In the
mathematical field of
graph theory
In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, the Pappus graph is a
bipartite
Bipartite may refer to:
* 2 (number)
* Bipartite (theology), a philosophical term describing the human duality of body and soul
* Bipartite graph, in mathematics, a graph in which the vertices are partitioned into two sets and every edge has an en ...
3-
regular undirected graph
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ve ...
with 18 vertices and 27 edges, formed as the
Levi graph of the
Pappus configuration
In geometry, the Pappus configuration is a configuration of nine points and nine lines in the Euclidean plane, with three points per line and three lines through each point.
History and construction
This configuration is named after Pappus of A ...
. It is named after
Pappus of Alexandria
Pappus of Alexandria (; grc-gre, Πάππος ὁ Ἀλεξανδρεύς; AD) was one of the last great Greek mathematicians of antiquity known for his ''Synagoge'' (Συναγωγή) or ''Collection'' (), and for Pappus's hexagon theorem i ...
, an ancient
Greek mathematician
Greek mathematics refers to mathematics texts and ideas stemming from the Archaic through the Hellenistic and Roman periods, mostly extant from the 7th century BC to the 4th century AD, around the shores of the Eastern Mediterranean. Greek mathe ...
who is believed to have discovered the "hexagon theorem" describing the Pappus configuration. All the
cubic distance-regular graphs are known; the Pappus graph is one of the 13 such graphs.
The Pappus graph has
rectilinear crossing number 5, and is the smallest cubic graph with that crossing number . It has
girth
Girth may refer to:
;Mathematics
* Girth (functional analysis), the length of the shortest centrally symmetric simple closed curve on the unit sphere of a Banach space
* Girth (geometry), the perimeter of a parallel projection of a shape
* Girth ...
6, diameter 4, radius 4,
chromatic number 2,
chromatic index 3 and is both 3-
vertex-connected and 3-
edge-connected. It has
book thickness 3 and
queue number 2.
The Pappus graph has a
chromatic polynomial equal to:
.
The name "Pappus graph" has also been used to refer to a related nine-vertex graph, with a vertex for each point of the Pappus configuration and an edge for every pair of points on the same line; this nine-vertex graph is 6-regular, is the
complement graph
In the mathematical field of graph theory, the complement or inverse of a graph is a graph on the same vertices such that two distinct vertices of are adjacent if and only if they are not adjacent in . That is, to generate the complement of a ...
of the union of three disjoint
triangle graphs, and is the complete tripartite graph K
3,3,3. The first Pappus graph can be embedded in the torus to form a self-
Petrie dual regular map with nine hexagonal faces; the second, to form a regular map with 18 triangular faces. The two regular toroidal maps are dual to each other.
Algebraic properties
The automorphism group of the Pappus graph is a group of order 216. It acts transitively on the vertices, on the edges and on the arcs of the graph. Therefore the Pappus graph is a
symmetric graph. It has automorphisms that take any vertex to any other vertex and any edge to any other edge. According to the ''Foster census'', the Pappus graph, referenced as F018A, is the only cubic symmetric graph on 18 vertices.
[ Conder, M. and Dobcsányi, P. "Trivalent Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Combin. Comput. 40, 41-63, 2002.]
The
characteristic polynomial
In linear algebra, the characteristic polynomial of a square matrix is a polynomial which is invariant under matrix similarity and has the eigenvalues as roots. It has the determinant and the trace of the matrix among its coefficients. The c ...
of the Pappus graph is
. It is the only graph with this characteristic polynomial, making it a graph determined by its spectrum.
Gallery
Image:Pappus graph colored.svg, Pappus graph coloured to highlight various cycles.
Image:Pappus graph 3color edge.svg, The chromatic index of the Pappus graph is 3.
Image:Pappus graph 2COL.svg, The chromatic number of the Pappus graph is 2.
Image:Pappus graph as regular map.png, The Pappus graph embedded in the torus, as a regular map with nine hexagonal faces.
Image:Pappus-graph-on-torus.png, The Pappus graph and associated map embedded in the torus.
References
{{reflist
Individual graphs
Regular graphs