離散数学の問題です

質問

三角形を持たない平面グラフには、四色定理が成り立つことを証明せよ。

この問題がわかりません。
教えて下さい。
お願いします。

回答No.1

Tacosan

「三角形」というのは, おそらく「3個の頂点 (とそれらをつなぐ 3本の辺) で囲まれる領域」のことだろう.

「平面グラフ」は「辺が交叉することなく平面上に描くことのできるグラフ」だな.

「四色定理」というのは, 本来は「平面グラフにおいては, たかだか 4色あれば辺の両端が同じ色にならないよう全ての頂点に色を割り当てることができる」という定理なんだが, 今の場合は前半を落とした「たかだか 4色あれば辺の両端が同じ色にならないよう全ての頂点に色を割り当てることができる」の部分のことをいってるんじゃないかな.