2つの単純な平面グラフの和集合は彩色数を持っています $\leq 12$

以来 $G_1$ そして $G_2$ 平面です、私たちは持っています $|E(G_1)| \le 3|V(G_1)|-6$ そして $|E(G_2)| \le 3|V(G_2)|-6$。以来$V(G_1) = V(G_2)$ 与えられて、 $V = V(G_1) = V(G_2)$便宜上。次に、$$|E(G_1)|+|E(G_2)| = |E(G_1 \cup G_2)| \le 6|V|-12$$ さて、握手補題によって、私たちはまた、 $$\sum_{v \in V}d_{G_1 \cup G_2}(v) = 2|E(G_1 \cup G_2)| \le 12|V| - 24$$ したがって、頂点が存在することが簡単にわかります。 $v \in V$ そのような $d_{G_1 \cup G_2}(v) < 12\ (*)$。今、私たちは帰納法を使用します$|V|$。

さて、 $|V| = 1$、結果は明確です（実際には $|V| \le 12$）。ここで、帰納的にそれが平面グラフに当てはまると仮定します。$|V| = n$。次に、で設定された頂点の場合$|V| = n+1$、頂点が設定されたグラフを考えてみましょう $V-v$（頂点を削除しても、平面グラフを非平面にすることはできないことに注意してください）。次に、帰納法の仮説により、このグラフを最大で色付けすることができます$12$色。今すぐ追加$v$エッジを削除して戻ります。沿って$(*)$、 $d_{G_1 \cup G_2}(v) < 12$ したがって、頂点が設定されたグラフで使用されている色の少なくとも1つで、この頂点に色を付けることができます。 $V-v$ これで完了です。

平面グラフは $|E(G)| \le 3|V(G)|-6$、したがって、2つの平面グラフの和集合は $|E(G)| \le 6|V(G)|-12$、次数未満の頂点があることを示すために使用できます $12$。

これは、帰納法による証明につながります。その頂点を削除し、残りを色付けしてから、その頂点に色を付けます。帰納的仮説が適用されるのは、$G$二つの平面グラフの和集合は：の対応するサブグラフ$G_1$ そして $G_2$。