情報数学 単純無向グラフについての問題

G が切断点を持てば,G は橋を持つ 　正しくない
G = (V, E) が連結,かつ |E| < |V | ならば,G は無向木である　正しい
すべての完全グラフの直径は 1 である　正しい
節点数 5 の完全グラフ K5 は平面描画可能である　正しくない
それぞれの理由を教えてほしいです。

No.1 ベストアンサー 回答者： alice_44 回答日時： 2012/08/20 22:30

G が切断点を持てば、G は橋を持つ → 正しくない

反例として、2 個の輪状グラフが 1 頂点を共有しているようなグラフ。

G = (V, E) が連結、かつ |E| < |V| ならば、G は無向木である　正しい
連結有向グラフの各頂点は流入辺を持ち、したがって |E| ≧ |V| である。
あとは、「連結無向グラフの辺の最小数は |E| = |V|-1 であり、そのとき
グラフは木である」を、頂点数についての帰納法で。

すべての完全グラフの直径は 1 である　正しい
「完全グラフ」と「直径」の定義より自明 …としか言いようがない。

節点数 5 の完全グラフ K5 は平面描画可能である　正しくない
辺が囲む領域の数を f と置くと、平面グラフについて
オイラーの公式 |V| - |E| + f = 2 が成り立つ。
また、単純グラフでは、辺が囲む各領域は頂点数 3 以上だから、
2|E| = 各領域を囲む辺数の総和 ≧ 3f でもある。
f を消去して 3|V| - |E| ≧ 6 だが、
K5 では、|V| = 5, |E| = 10 だから、この式は成り立たない。

この回答へのお礼

親切な解答ありがとうございます。

お礼日時：2012/08/21 01:15