Math 455  •  11 May 2009

Kuratowski's Theorem Examples

Copyright © 2009 by Murray Eisenberg.  All rights reserved.

Initialization

<<Combinatorica`

Three graphs: which, if any, are planar?

The code to create and display these three graphs is in the three closed cells below.

(Subscript[G, 1])=AddEdges[EmptyGraph[8],{{1,3},{1,7},{7,5},{5,3},{2,4},{2,8},{6,8},{4,6},{2,6},{4,5},{1,8},{3,7}}];  ShowGraph[(Subscript[G, 1]),VertexNumber->True,PlotLabel -> "Graph (Subscript[G, 1])",BaseStyle->16]

PlanarQ[(Subscript[G, 1])]

To create a planar embedding of a planar graph, you can move the vertices around if you use GraphPlot instead of ShowGraph: Once you obtain the output from GraphPlot, double-click the entire graphic. Then double-click one of the vertices and drag its bounding box around; the incident edges will follow with it.

GraphPlot[(Subscript[G, 1]),VertexLabeling->True,BaseStyle->16,ImageSize->7*72]

(Subscript[G, 2])=Graph[{{{1,2}},{{2,3}},{{3,4}},{{1,4}},{{5,6}},{{2,6}},{{1,6}},{{3,5}},{{4,5}}},{{{0.47959185,0.754717}},{{-1.0918367,0.754717}},{{-1.0918367,-1.0943396}},{{0.47959185,-1.0943396}},{{-0.3265306,0.18867925}},{{-0.3265306,-0.4779874}}}];
ShowGraph[(Subscript[G, 2]),VertexNumber->True,PlotLabel->"Graph (Subscript[G, 2])",BaseStyle->16]

(Subscript[K, 7])=CompleteGraph[7]; 
ShowGraph[(Subscript[K, 7]),VertexNumber->True,PlotLabel->"Graph (Subscript[K, 7])",BaseStyle->16]