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)) |