Pappus Graph

The Pappus graph is a cubic symmetric distance-regular graph on 18 vertices, illustrated above in three embeddings. It is Hamiltonian and can be represented in LCF notation as (Frucht 1976). It is the Levi graph of the configuration appearing in Pappus's hexagon theorem, namely the Pappus configuration. It is also Bouwer graph and honeycomb toroidal graph .

The Pappus graph is one of two cubic graphs on 18 nodes with smallest possible graph crossing number of 5 (the other being an unnamed graph denoted CNG 5B by Pegg and Exoo 2009), making it a smallest cubic crossing number graph (Pegg and Exoo 2009, Clancy et al. 2019).

It is also a unit-distance graph, as illustrated in the above embedding (Gerbracht 2008; E. Gerbracht, pers. comm., Jan. 2, 2010).

The plots above show the adjacency, incidence, and graph distance matrices for the Pappus graph.

The graph spectrum of the Pappus graph is . The following table summarizes a number of properties of the Pappus graph.

property	value
automorphism group order	216
characteristic polynomial
chromatic number	2
chromatic polynomial
claw-free	no
clique number	2
graph complement name	?
determined by spectrum	yes
diameter	4
distance-regular graph	yes
dual graph name	?
edge chromatic number	3
edge connectivity	3
edge count	27
edge transitive	yes
Eulerian	no
girth	6
Hamiltonian	yes
Hamiltonian cycle count	72
Hamiltonian path count	3024
integral graph	no
independence number	9
line graph	?
line graph name	?
perfect matching graph	no
planar	no
polyhedral graph	no
radius	4
regular	yes
square-free	yes
symmetric	yes
traceable	yes
triangle-free	yes
vertex connectivity	3
vertex count	18
vertex transitive	yes
weakly regular parameters	(18,(3),(0),(0,1))