☆ 予定では“グラフの彩色”まで進むことになっていたが，平面的グラフの話題だけで終わってしまった。次回は少しペースをあげる必要がありそうだ。
◎平面的な多重グラフ：辺を交差することなく平面上に描くことができるグラフ。
一方，辺を交差することなく平面上に描かれたグラフをこのテキストでは地図 (map) と読んでいる。脚注にもあるように平面グラフ (plane graph) と呼ばれるのが普通であるが，平面的グラフと平面グラフはよく似た表現なので，このテキストのように地図という，全く違う表現を使うことは初学者にとっては都合がいいと思う。
◎地図は平面をいくつかの領域に分割する。それぞれの領域の次数は，その領域を囲んでいる閉じた歩道を構成する辺の本数である。各辺は，必ず二つの領域を囲むので［定理 6.1］が成立する。ただし，図 6-2 の辺 {E, F} のように，辺が一つの領域内に含まれている場合の扱いには注意する必要がある。
◎オイラーの公式：連結な地図においては，[頂点の個数]−[辺の本数]＋[領域の個数]＝２ である。連結という条件があることに注意せよ。
◎最も小さい非平面的グラフ：
辺の本数が９以下のすべてのグラフは平面的グラフになる。辺の本数が 10 である非平面的グラフの例が K3,3 。なお，辺の本数が 10 以上の平面的グラフを作るのは簡単である。
頂点の個数が４以下のすべてのグラフは平面的グラフになる。頂点の個数が５である非平面的グラフの例が K5 。なお，頂点数が５以上の平面的グラフを作るのは簡単である。
◎クラトフスキーの定理：グラフが非平面的であるのは，K3,3 または K5 と同相な部分グラフを含むときかつそのときに限る。
★ピーターセングラフ (Petersen graph)：
まず，頂点数５の閉路（図 5-8 の右から２番目のグラフ）を少し大きめに書き，頂点に 1 から 5 の番号を順番につける。次にこの閉路の内側に，頂点 1 の近くに頂点 6，頂点 2 の近くに頂点 7，...，頂点 5 の近くに頂点 10 をそれぞれ作り，辺 {1, 6}, {2, 7}, {3, 8}, {4, 9}, {5, 10} をつけ加える。さらに，辺 {6, 8}, {8, 10}, {10, 7}, {7, 9}, {9, 6} をつけ加える。こうして出来上がったグラフをピーターセングラフという。
☆ピーターセングラフはハミルトングラフではない。ただし，このことを証明するのは少し難しい。
☆ピーターセングラフは非平面的グラフである：
ピーターセングラフから２つの辺 {3, 4} と {7, 10} を取り去ったグラフ（これはもとのグラフの部分グラフである）を G とする。
この部分グラフ G を次のようにして描きなおしてみる。
まず，頂点 1, 8, 9 を上の方に水平に並べ，頂点 2, 5, 6 を下に水平に並べる。
頂点 1 に接続している辺のもう一つの端点は 2 と 5 と 6 であるから，下に並んでいるそれぞれの頂点と直線で結ぶ。
次に，頂点 8 に接続している辺のうち，{8, 6} は直線で描く。辺 {8,3} は，頂点 8 と 2 を直線で結び，その途中に頂点 3 をつけ加える。頂点 8 と 5 も直線で結び，その途中に頂点 10 をつけ加える。頂点 9 からも同様にして辺を描く。
このようにして描くと，ピーターセングラフの部分グラフ G は K3,3 と同相であることが分かる。よって，ピーターセングラフはクラトフスキーの定理から
非平面的グラフである。