Pappus Graph

The Pappus graph is a cubic symmetric distance-regular graph on 18 vertices, illustrated above in a number of drawings. It is a Hamiltonian graph 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. 2020).

It is also a unit-distance graph, as illustrated in a number of unit-distance embeddings, the first of which is due to Gerbracht (2008; E. Gerbracht, pers. comm., Jan. 2, 2010).

The Pappus graph is toroidal, as illustrated above. The left-hand drawing shows a graph embedding in a fundamental region whose paired boundary sides are identified to form a torus. The right-hand drawing shows a finite patch of the corresponding periodic lift, illustrating how edges continue across these boundaries and where corresponding vertices in different regions represent the same vertex on the torus.

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

The graph spectrum of the Pappus graph is .

The Pappus graph is implemented in the Wolfram Language as GraphData["PappusGraph"].