グラフについて質問です

C個の連結成分からなるどのようなグラフでも以下の関係式を満たすことを示せ。
V-I＋L＝C
ただし、Vは頂点の数、Iは内線の数、Lはループの数である。

自分でいろいろなグラフを書いてみるといつでも上式が成り立つことは確認できました。ただ、この式が成立することを証明するのは私にはできないのです。

No.2 回答者： 銀鱗 回答日時： 2022/03/09 19:42

じゃあ、「関係式を満たせません」と答えれば良い。

どこかに例外的な条件を満たさないパターンがあるかもしれませんからね。

・・・

質問文では「証明できない」と主張していらっしゃいます。
ならば回答はそれにならうべきです。

そうではなく、どう証明すればよいのかを聞きたいのであれば、そのように質問しましょう。
照明方法を聞きたいのではなく、代わりに証明して欲しいという事であればそのように質問文に書きましょう。
例えば、
「代わりに解け。オレ様が解いたことにして提出してやるｗｗｗ」
てね。

なお、ここは代わりに作業を依頼する場所ではありません。
自力で問題を解くためのアドバイスをもらう場所です。


・・・余談・・・

この手の証明はちょっと面倒なんだ。
とりあえず四角形から頂点の数を増やしてI/L/Cがどんなパターンで増えるのかを視覚的に確認できるようにしてみましょう。
そこから規則性を見つけて証明するんです。

No.1 回答者： Tacosan 回答日時： 2022/03/09 19:38

たぶん C=1 で証明すれば十分で, かつ頂点数かなんかで帰納法を回すことになるんだろうけど....

「内線」「ループ」ってどう定義しているんだろう.

この回答へのお礼

内線は２つの頂点を結ぶ線だと思います。
ループの正確な定義はわかりかねます。

お礼日時：2022/03/09 19:44