Construction of the Grötzch graph

The Grötzch graph may be built by taking the complete graph K5, choosing a cycle of length 5 (say, 1-3-5-2-4), inserting a vertex of degree two on each chord of this cycle, and finally connecting each of these vertices to a new vertex.

> G := CompleteGraph(5);
> E := EdgeSet(G);
> H := InsertVertex({ E | { 1, 3 }, { 1, 4 }, { 2, 4 }, { 2, 5 }, { 3, 5 } });
> L,V := Union(H, CompleteGraph(1));
> L := L + { { V.11, V.6 }, { V.11, V.7 }, { V.11, V.8 }, { V.11, V.9 },
>             { V.11, V.10 } };
> L;

Graph
Vertex  Neighbours

1       2 5 6 7 ;
2       1 3 8 10 ;
3       2 4 6 9 ;
4       3 5 7 8 ;
5       1 4 9 10 ;
6       1 3 11 ;
7       1 4 11 ;
8       2 4 11 ;
9       3 5 11 ;
10      2 5 11 ;
11      6 7 8 9 10 ;

Next Group: Automorphism group of the 8-dimensional cube Previous Group: Construction of Tutte's 8-cage