Petersen’s Theorem

Author

Eric W. Weisstein
April 2, 2013

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/PetersensTheorem.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/PetersensTheorem.html.

©2013 Wolfram Research, Inc. except for portions noted otherwise

Examples

g=Select[GraphData[{"Cubic","NoPerfectMatching"}],GraphData[#,"BridgeCount"]>2&]

GraphData/@g

GraphData[g[[1]],"LabeledImage"]

g1=IndexGraph[Subgraph[GraphData[g[[1]]],{2,3,4,5,13}]]

RecognizeGraph[g1]

GraphData[{5,31},"Images"]

e={2-#[[1]],#[[2]]}&/@GraphData[{5,31},"VertexCoordinates"]

edges=GraphData[{5,31},"EdgeList"]

v=Join@@Table[RotationMatrix[π/2+2π i/3].#&/@e,{i,0,2}]

gnew=System`Graph[Range[16],Join[Join@@Table[edges/.n_Integer:>n+5i,{i,0,2}],16\[UndirectedEdge]#&/@{4,9,14}],VertexCoordinates->(vs=Append[v,{0,0}])]

RecognizeGraph[%]

vnew=vs[[FindGraphIsomorphism[GraphData[{"Cubic",{16,14}}],gnew][[All,2]]]]

System`Graph[Range[16],GraphData[{"Cubic",{16,14}},"EdgeList"],VertexCoordinates->vnew,System`EdgeStyle->Black,System`VertexSize->Scaled[.03],System`VertexStyle->Red,ImageSize->300]