グラフ理論の質問の証明

Question

私はこの声明に関する証拠を思い付くことができません-

Gを接続された平面グラフと見なします。Gが2部グラフでない場合、Gの平面埋め込みには、奇数次数の面が少なくとも2つあります。

誰かが証明を手伝ってくれませんか？

Answer 1

Gは2部グラフではないため、Gには奇数サイクルCが含まれます。 $F_{1},F_{2},......,F_{k}$平面埋め込みのCの内側の面になります。これらの顔の次数の合計を考慮してください。

• Cの各エッジは1回カウントされます。
• Dを任意の境界上のエッジのセットとします $F_{i}$、ただしCではありません。

Dの各エッジは2回カウントされます。

そう $\sum_{i}$ $\deg(F_{i})$ = $|E(C)| + 2|D|$

以来 $|E(C)|$ 奇妙で $2|D|$ でも、

$\sum_{i}$ $\deg(F_{i})$ 奇妙なので $\deg(F_{i})$ 一部の人にとっては奇妙でなければなりません $i$

したがって、C内の少なくとも1つの面の次数が奇数になります。

同じ引数を使用して、少なくとも1回はCの外側の面の次数が奇数であることを示すことができます。