Georges Graph

Author

Eric W. Weisstein
April 20, 2022

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

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

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

Graphic

Default

GraphData["GeorgesGraph"]//StyleGraphs

All

GraphData["GeorgesGraph","Graph","All"]//StyleGraphs

LCF

GraphData["GeorgesGraph","LCFSignature"]

GraphData["GeorgesGraph","Graph","LCF"]//StyleGraphs

UnitDistance

GraphData["GeorgesGraph","UnitDistance"]

UnitDistanceGraphQ[GraphData["GeorgesGraph"],Debug->True]//Timing

GraphData["GeorgesGraph","Graph","UnitDistance"]//StyleGraphs

Select[%,!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&]

Select[UnitDistanceEmbeddingRefine/@Complement@@(GraphData["GeorgesGraph","Graph",#]&/@{"All","UnitDistance"}),UnitDistanceGraphEmbeddingQ]

FindUnitDistanceEmbedding[GraphData["GeorgesGraph"],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

{"GeorgesGraph",l=FindSubgraphUnitDistanceEmbedding[GraphData["GeorgesGraph"],TimeConstraint->300,"Results"->All]//Timing}

gs=UniqueEmbeddings[l]

Matchstick

GraphData["GeorgesGraph","Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData["GeorgesGraph",{"RCN","CN"}]

GraphData["GeorgesGraph","Graph","MinimalCrossing"]//StyleGraphs

3D

Graph3D[GraphData["GeorgesGraph","Edges"]]

Default embedding

g=Graph@GraphData["GeorgesGraph","Edges"]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

MinimalCrossing Construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData["GeorgesGraph"],"CrossingNumber"->12]]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

Grünbaum

Import["/Users/eww/Downloads/3-connected non-Hamilt n_3.pdf",{"Pages",4}]

GraphPlot[g,Method->None]

ShowLabeledGraph[g=AddEdges[AddVertices[DeleteEdges[GraphUnion[Graph[{"Prism",6}],Graph[{"Prism",6}]],{{11,5},{4,10},{1,7},{2,8},{17,23},{16,22},{19,13},{14,20},{12,6},{3,9},{24,18},{15,21},{11,10},{23,22},{5,4},{17,16}}],{
{.32,.82},{.44,.82},{.56,.82},{.7,.82},{2.32,.82},{2.44,.82},{2.56,.82},{2.7,.82},
{.32,.18},{.44,.18},{.56,.18},{.7,.18},{2.32,.18},{2.44,.18},{2.56,.18},{2.7,.18},
{.15,.5},{.85,.5},{2.15,.5},{2.85,.5},
{1.5,.7},{1.5,.3},{1.3,.9},{1.7,.9},{1.3,.1},{1.7,.1}
}],
{{11,25},{25,5},{4,28},{28,10},{25,26},{26,27},{27,28},
Sequence@@Partition[Range[33,36],2,1],{7,33},{33,1},{2,36},{36,8},Sequence@@Partition[Range[29,32],2,1],
Sequence@@Partition[Range[37,40],2,1],{12,41},{41,6},{3,42},{42,9},{24,43},{43,18},{15,44},{44,21},{19,37},{37,13},{20,40},{40,14},{17,29},{29,23},{16,32},{32,22},{47,45},{45,48},{46,49},{46,50},{46,45},
{47,27},{48,31},{48,35},{47,39},{41,42},{43,44},{49,38},{50,26},{50,30},{49,34},{11,4},{10,5},{22,17},{23,16}}],
VertexStyle->Disk[.02],ImageSize->700]

Through[{V,M}[g]]

RecognizeGraph[g]

Degrees[g]

Properties

GraphData["GeorgesGraph","Classes"]

GraphData["GeorgesGraph","Traceable"]

GraphData["GeorgesGraph","HamiltonianPaths"]

Length[h=FindHamiltonianPath[Graph["GeorgesGraph"],All]]//Timing

GraphData

GraphDataString

Print[GraphDataString[g,
"StandardName"->"GeorgesGraph",
"Name"->"Georges graph",
"Classes"->{"Nonhamiltonian"},
"Information"->"GeorgesGraph",
Debug->True,
TimeConstraint->120
]]