gm learning

平面に描けるグラフ

　ここに謎のグラフが８個並んでいます．いずれのグシャグシャな感じで，たくさんの辺が交差していますね．

　その交差の数をできるだけ減らしていって，見やすい姿に変えてください．すると，それぞれのグラフの正体が明らかになるでしょう．

　はたして，交差の数をいくつまで減らせるでしょうか？

　実は，それぞれのグラフの正体は次のとおりです．交差の数を表に示した最小値にできましたか？

　グラフ４からグラフ８のように，平面の上に辺どうしの交差がないように描くことができるグラフのことを平面的グラフと言います．逆に，辺の交差なしでは，平面に描くことができないグラフのことは 非平面的グラフと言います．