SageMathでグラフ理論(クラトウスキーの定理）

THEOREM 12.2(Kuratowski, 1930). A graph is planar if and only if it contains no subgraph homeomorphic to $K_5$ or $K_{3,3}$ .

グラフ $G$ が平面グラフであるための必要十分条件は $G$ が $K_5$ または $K_{3,3}$ と位相同型な部分グラフを含まないことである。

THEOREM 12.3 A graph is planar if and only if it contains no subgraph contractible to $K_5$ or $K_{3,3}$ .

contractibleというのは、頂点を重ねること(縮約)によって頂点と辺の数をへらしていくことで、例として、Petersenグラフの内側の5つの点を外側に重ね合わせると次のようになります。

# pertsen.sage

G=graphs.PetersenGraph()
p1=plot(G)

G2=copy(G)

G2.merge_vertices([0,5])
G2.merge_vertices([1,6])
G2.merge_vertices([2,7])
G2.merge_vertices([3,8])
G2.merge_vertices([4,9])
p2=plot(G2)
# graphics_array( (p1,p2))

f:id:niming538:20170929154119p:plain