Grötzsch Graph

Author

Eric W. Weisstein
December 19, 2025

This notebook downloaded from https://mathworld.wolfram.com/notebooks/GraphTheory/GroetzschGraph.nb.

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

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

Figure

GraphicsGrid[Partition[GraphData["GrotzschGraph","Graph","All"]//StyleGraphs,UpTo[5]],Dividers->All]

Embeddings

<<MathWorld`Graphs`

Names

GraphData["GrotzschGraph","StandardName"]

GraphData["GrotzschGraph","StandardNames"]

HouseOfGraphs

hogid=GraphData["GrotzschGraph","NotationRules","HouseOfGraphs"]

HouseOfGraphsLookup[hogid]

HouseOfGraphsGraph[hogid]//StyleGraphs[#,ImageSize->Small]&

Primary

GraphData["GrotzschGraph"]//StyleGraphs[#,ImageSize->Small]&

Construction from Read and Wilson

All

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

CurvedEdge

GraphData["GrotzschGraph","Graph","CurvedEdge"]//StyleGraphs

Inexact

Select[GraphData["GrotzschGraph","Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData["GrotzschGraph","EdgeList"]]

Default embedding

GraphPlot@GraphData["GrotzschGraph","Edges"]

v=Join[CirclePoints[5],CirclePoints[1/2,5],{{0,0}}];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,3,4,5,1,10,4,8,2,6,11,8],e[5,9,3,7,1],e[10,11,7],{9,11},{5,6}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Norm@Mean[v[[{2,4}]]]

v=FullSimplify@Join[CirclePoints[5],CirclePoints[(1/4) (-1+(Sqrt[5])),5],{{0,0}}];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,3,4,5,1,10,4,8,2,6,11,8],e[5,9,3,7,1],e[10,11,7],{9,11},{5,6}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Norm@FullSimplify[RegionIntersection[Line[v[[{10,8}]]],Line[v[[{9,7}]]]]][[1,1]]//FullSimplify

v=Join[CirclePoints[{(2/(3+(Sqrt[5]))),-Pi/2},5],CirclePoints[1,5],{{0,0}}];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,6,2,7,3,8,4,9,5,10,1,3,5,2,4,1],Sequence@@Table[{11,i},{i,6,10}]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

v=Join[CirclePoints[{1,-Pi/2},5],CirclePoints[1,5],{{0,0}}];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,6,2,7,3,8,4,9,5,10,1,3,5,2,4,1],Sequence@@Table[{11,i},{i,6,10}]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

gs={,,}

Degenerate

GraphData["GrotzschGraph","Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData["GrotzschGraph","Graph","Degenerate"]

Bilateral

GraphData["GrotzschGraph","Graph","Bilateral"]//StyleGraphs

Grid[DeleteCases[Monitor[{g=#,BilateralGraphEmbeddingTypes[#],GraphSymmetryGroup[#]}&/@GraphData["GrotzschGraph","Graph","All"],g],{_,_,TransformationGroup[{}]}],Dividers->All,Alignment->{{Center,{Left}}}]//Quiet

Circular

GraphData["GrotzschGraph","Graph","Circular"]//StyleGraphs

Circular construction All

GraphData["GrotzschGraph","Hamiltonian"]

GraphData["GrotzschGraph","LCF"]

GraphData["GrotzschGraph","HamiltonianCycleCount"]

Length[hc=FindHamiltonianCycle[GraphData["GrotzschGraph"],All][[All,All,1]]]//Timing

(circ=CircularEmbeddingFromHamiltonianCycle[GraphData["GrotzschGraph"],#]&/@hc);//Timing

circ

GraphWithSymmetryGroups={#,GraphSymmetryGroup[#]}&/@circ;//Timing

Tally[GraphWithSymmetryGroups[[All,-1]]]//Column

(BilateralOrRotationalGraphs={BilateralGraph[#,"ReturnNonbilateralGraph"->True],#2}&@@@SortBy[
DeleteCases[GraphWithSymmetryGroups,{_,TransformationGroup[{}]}],
{MatchQ[#[[2]],TransformationGroup[{_Rotation,r_Reflection}|{r_Reflection|_Rotation}]],FirstCase[#[[2]],Rotation[{0,0},r_]:>N[r/π],{},{0,∞}]}&
])//Timing

Length[SymmetricGraphs=DeleteDuplicatesBy[BilateralOrRotationalGraphs,CircularCanonicalGraphEmbedding[#[[1]]]&]]//Timing

SymmetricGraphs

Length[BilateralGraphs=Select[SymmetricGraphs,!FreeQ[#,Reflection]&][[All,1]]]

BilateralGraphs

Length[BilateralAndRotationalGraphs=Select[SymmetricGraphs,And[!FreeQ[#,Rotation],!FreeQ[#,Reflection]]&][[All,1]]]

BilateralAndRotationalGraphs

Planar

GraphData["GrotzschGraph","Planar"]

GraphData["GrotzschGraph","Graph","Planar"]//StyleGraphs

MinimalCrossingNumber crossings.uos.de [verified 5]

CrossingNumber[GraphData["GrotzschGraph"],Method->"WebCompute"]//AbsoluteTiming

DateString[]

MinimalCrossing

GraphData["GrotzschGraph","CN"]

(gs=GraphData["GrotzschGraph","Graph","MinimalCrossing"])//StyleGraphs

GraphCrossingCount/@gs

GraphCrossingDiagram/@gs

MinimalCrossing construction Tutte

(cn=CrossingNumber[GraphData["GrotzschGraph"],TimeConstraint->1])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData["GrotzschGraph"],"CrossingNumber"->cn])//PolyhedralGraphQ//AbsoluteTiming

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

TutteGraphs=BilateralGraph[CenterGraph@IGLayoutTutte[g,"OuterFace"->#],"ReturnNonbilateralGraph"->True]&/@faces

TutteGraphsWithOuterCrossingPointCounts={
#,
Count[OuterFace[#],_?(GreaterThan[GraphData["GrotzschGraph","V"]])]
}&/@TutteGraphs;

Cases[TutteGraphsWithOuterCrossingPointCounts,{g_,0}:>g]

Select[Cases[TutteGraphsWithOuterCrossingPointCounts,{g_,1}:>g],Length[OuterFace[#]]>3&]

TutteGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[
#,
AdditionalData->Join[Table[True,GraphData["GrotzschGraph","V"]],Table[False,cn]],
SameTest->Equal
]
}&/@TutteGraphs;

SymmetricEmbeddingsWithOperations=DeleteCases[
TutteGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]

Select[SymmetricEmbeddingsWithOperations[[All,1]],Count[OuterFace[#],_?(GreaterThan[GraphData["GrotzschGraph","V"]])]==0&]

MinimalCrossing construction Random 500

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData["GrotzschGraph"],"CrossingNumber"->cn,RandomSeed->n]],{n,500}],Max[OuterFace[#]]<=GraphData["GrotzschGraph","V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData["GrotzschGraph"],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

GraphPlot@RotateGraph[,-4Pi/5]

h1=v[[4,2]];
h2=v[[5,2]];

v=Join[UnitCirclePoints[5],{{0,h1}},Subdivide[{-1/2,-1/4},{1/2,-1/4},4]];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,3,4,5,1,11,10,9,8,7,5,10,3,8,1],e[4,6,2],{6,9},e[7,6,11]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

GraphPlot@

h1=v[[4,2]];
h2=v[[5,2]];

v=Join[UnitCirclePoints[5],{{0,h1}},Subdivide[{-1/2,0},{1/2,0},2],Mean[v[[{6,#}]]]&/@{7,9}];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,3,4,5,1,9,11,6,10,7,5,11],e[7,3,9],e[4,6,2],{1,10},e[7,8,9],{6,8}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

gs={,}

MinimalCrossing construction Random 1000

(cn=CrossingNumber[GraphData["GrotzschGraph"],TimeConstraint->1])//AbsoluteTiming

(RandomGraphs=Table[MinimalCrossingGraph[GraphData["GrotzschGraph"],"CrossingNumber"->cn,RandomSeed->n],{n,1000}]//Union);//Timing

RandomGraphsWithOuterCrossingPointCounts={
#,
Count[OuterFace[#],_?(GreaterThan[GraphData["GrotzschGraph","V"]])]
}&/@RandomGraphs;

Small numbers of crossing points on the boundary:

Cases[RandomGraphsWithOuterCrossingPointCounts,{g_,0}:>g]

Select[Cases[RandomGraphsWithOuterCrossingPointCounts,{g_,1}:>g],Length[OuterFace[#]]>3&]

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[
#,
AdditionalData->Join[Table[True,GraphData["GrotzschGraph","V"]],Table[False,cn]],
SameTest->Equal
]
}&/@RandomGraphs;

DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]/.g_Graph:>BilateralGraph[CenterGraph@g,"ReturnNonbilateralGraph"->True]

v=Append[CirclePoints[{1,Pi/2},10],{0,0}];
ee=Join[{e[{1,10},1]},Table[{i,11},{i,2,10,2}]];
g0=Graph[Range@Length@v,UndirectedEdge@@@ee,VertexCoordinates->v,VertexLabels->Automatic]

{EdgeCount[g0],GraphData["GrotzschGraph","M"]}

Length[subsets=Subsets[Subsets[Range[1,9,2],{2}],{5}]]

adde=Select[subsets,IsomorphicGraphQ[GraphData["GrotzschGraph"],EdgeAdd[g0,UndirectedEdge@@@#]]&]

v=Append[CirclePoints[{1,Pi/2},10],{0,0}];
ee=Join[{e[{1,10},1]},Table[{i,11},{i,2,10,2}],{{1,5},{1,7},{3,7},{3,9},{5,9}}];
g=Graph[Range@Length@v,UndirectedEdge@@@ee,VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

{#,{{0,3/2},{1,3/2}}}&/@{{1,5},{1,7},{3,7},{3,9},{5,9}}

v=Append[CirclePoints[{1,Pi/2},10],{0,0}];
ee=Join[{e[{1,10},1]},Table[{i,11},{i,2,10,2}],{{1,5},{1,7},{3,7},{3,9},{5,9}}];
curvededges={{{1,5},{{0,-(3/2)},{1,-(3/2)}}},{{1,7},{{0,(3/2)},{1,(3/2)}}},{{3,7},{{0,-(3/2)},{1,-(3/2)}}},{{3,9},{{0,(3/2)},{1,(3/2)}}},{{5,9},{{0,-(3/2)},{1,-(3/2)}}}};
g=CurvedEdgeAnnotate[
Graph[Range@Length@v,UndirectedEdge@@@ee,VertexCoordinates->v,VertexLabels->Automatic],
curvededges
]

RecognizeGraph@g

GraphCrossingCount@g

GraphCrossingDiagram@g

MinimalRectilinearLocalCrossing

GraphData["GrotzschGraph",{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData["GrotzschGraph","Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

MinimaRectilinearlLocalCrossing construction 1000

AdjacentCrossingsQ[g_Graph,cn_Integer]:=Module[{a=AdjacencyList[g],n=VertexCount[g]-cn},Max[Take[a,-cn]]>n]

(cn=CrossingNumber[GraphData["GrotzschGraph"],TimeConstraint->10])//AbsoluteTiming

(gs=Select[Table[MinimalCrossingGraph[GraphData["GrotzschGraph"],"CrossingNumber"->cn,RandomSeed->i],{i,1000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

MinimaRectilinearlLocalCrossing construction 20000

AdjacentCrossingsQ[g_Graph,cn_Integer]:=Module[{a=AdjacencyList[g],n=VertexCount[g]-cn},Max[Take[a,-cn]]>n]

(cn=CrossingNumber[GraphData["GrotzschGraph"],TimeConstraint->10])//AbsoluteTiming

(gs=Select[Table[MinimalCrossingGraph[GraphData["GrotzschGraph"],"CrossingNumber"->cn,RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Circulant

GraphData["GrotzschGraph","Circulant"]

GraphData["GrotzschGraph","Graph","Circulant"]//StyleGraphs

Halin

GraphData["GrotzschGraph","Halin"]

GraphData["GrotzschGraph","Graph","Halin"]//StyleGraphs

Rigid

GraphData["GrotzschGraph","Rigid"]

GraphData["GrotzschGraph","Graph","Rigid"]//StyleGraphs

Flexible

GraphData["GrotzschGraph","Flexible"]

GraphData["GrotzschGraph","Graph","Flexible"]//StyleGraphs

LCF

GraphData["GrotzschGraph","LCF"]

GraphData["GrotzschGraph","HamiltonianCycleCount"]

GraphData["GrotzschGraph","LCFSignature"]

GraphData["GrotzschGraph","LCFNotations"]

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

UnitDistance

GraphData["GrotzschGraph","UnitDistance"]

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

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

UnitDistance by refinement of default embeddings

Graph[edge list]

(g=UnitDistanceEmbeddingRefine[Graph[GraphData["GrotzschGraph","EdgeList"]],MaxIterations->500])//Timing

UnitDistanceGraphEmbeddingQ[g]

Graph[vertex list, edge list]

(g=UnitDistanceEmbeddingRefine[Graph[GraphData["GrotzschGraph","VertexList"],GraphData["GrotzschGraph","EdgeList"]],MaxIterations->500])//Timing

UnitDistanceGraphEmbeddingQ[g]

UnitDistance by refinement of existing embeddings

gs=UnitDistanceEmbeddingRefine[#,MaxIterations->500]&/@Complement@@(GraphData["GrotzschGraph","Graph",#]&/@{"All","UnitDistance"})

TextGrid[
gdata=SortBy[
{#,DegenerateGraphEmbeddingQ[#],GraphSymmetryGroup[#],Max[Abs[EdgeLengths[#]-1]]}&/@gs,
Last
],
Dividers->All
]

Cases[gdata,{__,0.}]

Symmetric:

gs=Cases[
gdata,
{g_,_,sym:Except[TransformationGroup[{}]],diff_}:>{
HighlightGraph[g1=BilateralGraph[CenterGraph[g],"ReturnNonbilateralGraph"->True],Flatten[FindCoincidentVertices[g1]]],
sym,
diff
}]

GraphPlot@

EdgeLengths@

RotateGraph[,{8,11}]

v=UnitCirclePoints[8,Pi/2];
v=Join[v,{v[[3]]+RotationMatrix[-Pi/2].(v[[6]]-v[[3]]),v[[6]]+RotationMatrix[Pi/2].(v[[3]]-v[[6]])}];
v=FullSimplify[Join[v,{{-#,#2}&@@v[[9]]}]];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,5,8,3,6,1,4,7,2,5,9,3],e[9,10,11,7,3],e[5,11],e[8,4,10,6,2]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

UnitDistance by FindUnitDistanceEmbedding

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

UnitDistance by FindUnitDistanceEmbedding  (random embeddings returning on messages)

gs=FindUnitDistanceEmbedding[GraphData["GrotzschGraph"],50,"ReturnWithMessage"->True];//Quiet//Timing

gdata=SortBy[
{#,Max[Abs[EdgeLengths[#]-1]]}&/@gs,
Last
]

Cases[gdata,{g_?UnitDistanceGraphEmbeddingQ,_}:>g]

SymmetricEmebddings=Select[gdata,GraphSymmetryGroup[#[[1]]]=!=TransformationGroup[{}]&]

UnitDistance by FindUnitDistanceEmbedding  (random embedding waiting until UD is found)

FindUnitDistanceEmbedding[GraphData["GrotzschGraph"],"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData["GrotzschGraph","Matchstick"]

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

3D default

Graph3D[GraphData["GrotzschGraph","Edges"]]

3D All

GraphData["GrotzschGraph","Graph",{"3D","All"}]

3D UnitDistance construction Random

GraphData["GrotzschGraph","Dimension"]

(g=UnitDistanceEmbeddingRefine[Graph3D[Range[GraphData["GrotzschGraph","V"]],GraphData["GrotzschGraph","Edges"]],WorkingPrecision->50])//Timing

UnitDistanceGraphEmbeddingQ[g]

3D UnitDistance construction pentagram

Based on the random one found above

v=Join[Append[#,0]&/@CirclePoints[{(Sqrt[(2/(5+(Sqrt[5])))]),0},5],Append[#,1]&/@CirclePoints[{1,-Pi},5],{{0,0,2}}];
ee=Join[{e[1,3,5,2,4,1]},Table[{i,11},{i,6,10}],{e[8,1,9,2,10,3,6,4,7,5,8]}];
g=Graph[Range@Length@v,UndirectedEdge@@@ee,VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

v=Join[Append[#,0]&/@CirclePoints[{(Sqrt[(2/(5+(Sqrt[5])))]),0},5],Append[#,h]&/@CirclePoints[{r,-Pi},5],{{0,0,z}}];
ee=Join[{e[1,3,5,2,4,1]},Table[{i,11},{i,6,10}],{e[8,1,9,2,10,3,6,4,7,5,8]}];
g=Graph[Range@Length@v,UndirectedEdge@@@ee,VertexCoordinates->v,VertexLabels->Automatic];

eqn=DeleteCases[UnitEdgeEquations[v,UndirectedEdge@@@ee]//FullSimplify//Union,True]

z == 3/2:

eqn2=Append[eqn,z==3/2]

soln2=Solve[eqn2,{r,h,z},PositiveReals][[1]]//RootReduce

v=Join[Append[#,0]&/@CirclePoints[{(Sqrt[(2/(5+(Sqrt[5])))]),0},5],Append[#,h]&/@CirclePoints[{r,-Pi},5],{{0,0,z}}]/.soln2;
ee=Join[{e[1,3,5,2,4,1]},Table[{i,11},{i,6,10}],{e[8,1,9,2,10,3,6,4,7,5,8]}];
g=Graph[Range@Length@v,UndirectedEdge@@@ee,VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

UnitDistanceGraphEmbeddingQ@g

soln2//InputForm

z == 2h:

eqn3=Append[eqn,z==2h]

soln3=Solve[eqn1,{r,h,z},PositiveReals][[1]]//RootReduce

v=Join[Append[#,0]&/@CirclePoints[{(Sqrt[(2/(5+(Sqrt[5])))]),0},5],Append[#,h]&/@CirclePoints[{r,-Pi},5],{{0,0,z}}]/.soln3;
ee=Join[{e[1,3,5,2,4,1]},Table[{i,11},{i,6,10}],{e[8,1,9,2,10,3,6,4,7,5,8]}];
g=Graph[Range@Length@v,UndirectedEdge@@@ee,VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

UnitDistanceGraphEmbeddingQ@g

z == h:

eqn4=Append[eqn,z==h]

soln4=Solve[eqn4,{r,h,z},PositiveReals][[1]]//RootReduce

v={#,#2,-#3}&@@@(Join[Append[#,0]&/@CirclePoints[{(Sqrt[(2/(5+(Sqrt[5])))]),0},5],Append[#,h]&/@CirclePoints[{r,-Pi},5],{{0,0,z}}]/.soln4);
ee=Join[{e[1,3,5,2,4,1]},Table[{i,11},{i,6,10}],{e[8,1,9,2,10,3,6,4,7,5,8]}];
g=Graph[Range@Length@v,UndirectedEdge@@@ee,VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

UnitDistanceGraphEmbeddingQ@g

3D UnitDistance construction pentagon (de Grey)

de Grey, A.~D.~N.~J.  ``A 5-Chromatic, Triangle-Free Unit-Distance Graph in $\R^3$ With 61 Vertices.'' {\it Geombinatorics}, 2026.

v=Join[Append[#,0]&/@UnitCirclePoints[5,0],Append[#,.3]&/@CirclePoints[{.3,Pi},5],{{0,0,6/5}}];
ee={e[10,{1,5},1,7,3,9,5,6,2,8,4,10,11,9],e[6,11,7],e[8,11]};
g=Graph[Range[Length[v]],UndirectedEdge@@@ee,VertexCoordinates->v,VertexLabels->Automatic]

col=MapIndexed[Style[#2[[1]],{Blue,Yellow,Red,DarkGreen,Purple}[[#]]]&,FindVertexColoring[g]];

HighlightGraph[g,col]

v=Join[Append[#,0]&/@UnitCirclePoints[5,0],Append[#,h]&/@CirclePoints[{r,Pi},5],{{0,0,z}}];
ee={e[10,{1,5},1,7,3,9,5,6,2,8,4,10,11,9],e[6,11,7],e[8,11]};

eqn=DeleteCases[UnitEdgeEquations[v,UndirectedEdge@@@ee]//FullSimplify,True]//Union

z == 6/5:

eqn1=Append[eqn,z==6/5]//FullSimplify

soln1=Solve[eqn1,{h,r,z},PositiveReals][[1]]//FullSimplify

v=Join[Append[#,0]&/@UnitCirclePoints[5,0],Append[#,h]&/@CirclePoints[{r,Pi},5],{{0,0,z}}]/.soln1;
ee={e[10,{1,5},1,7,3,9,5,6,2,8,4,10,11,9],e[6,11,7],e[8,11]};
g=Graph[Range[Length[v]],UndirectedEdge@@@ee,VertexCoordinates->v]

RecognizeGraph[g]

UnitDistanceGraphEmbeddingQ[g]

z == 1

eqn2=Append[eqn,z==1]//FullSimplify

soln2=Solve[eqn2,{h,r,z},PositiveReals][[1]]//FullSimplify

v=Join[Append[#,0]&/@UnitCirclePoints[5,0],Append[#,h]&/@CirclePoints[{r,Pi},5],{{0,0,z}}]/.soln2;
ee={e[10,{1,5},1,7,3,9,5,6,2,8,4,10,11,9],e[6,11,7],e[8,11]};
g=Graph[Range[Length[v]],UndirectedEdge@@@ee,VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

UnitDistanceGraphEmbeddingQ[g]

3D UnitDistance

GraphData["GrotzschGraph","Graph",{"3D","UnitDistance"}]

GraphicsRow[GraphData["GrotzschGraph","Graph",{"3D","UnitDistance"}],ImageSize->400]

3D Polyhedron

GraphData["GrotzschGraph","Polyhedral"]

GraphData["GrotzschGraph","Graph",{"3D","Polyhedron"}]

Properties

Classes

GraphData[g,"Classes"]

Matrices

GraphicsRow[GraphMatrixPlot[GraphData["GroetzschGraph"]]]

Properties

GraphData[g,"Missing"]

GraphData[g,{"V","M"}]

TableForm[GraphDataTable[g,x],TableDepth->2]//TraditionalForm

GraphData

GraphDataClassString

GraphDataClassString[GraphData["GrotzschGraph","Classes"]]