Fact-checked by Grok 2 weeks ago

Petersen graph

The Petersen graph is a 3-regular (cubic) graph with 10 vertices and 15 edges, serving as the unique (3,5)-cage graph—the smallest graph of girth 5 in which every vertex has degree 3.^[1] It can be constructed in multiple ways, including as the complement of the line graph of the complete graph K_5, as the odd graph O_3 (vertices representing 2-element subsets of a 5-element set, with edges between disjoint subsets), or as the generalized Petersen graph P(5,2).^[1] Introduced by Danish mathematician Julius Petersen in 1898 as a counterexample to a conjecture on the edge-coloring of cubic graphs, it was also implicitly described earlier in 1886 by Alfred Kempe in connection with the Desargues configuration.^[1] Renowned for its symmetries, the Petersen graph is vertex-transitive and edge-transitive, with an automorphism group of order 120 isomorphic to the symmetric group S_5.^[1] Key structural properties include a girth of 5 (no cycles shorter than 5 vertices), diameter 2 (any two vertices are at most distance 2 apart), chromatic number 3, and edge chromatic number 4, classifying it as a Class II graph under Vizing's theorem.^[1] It is non-planar (with crossing number 2), non-Hamiltonian (lacking a cycle through all vertices), yet hypohamiltonian (removing any vertex yields a Hamiltonian graph), making it a foundational example in extremal graph theory.^[1] The Petersen graph plays a pivotal role in numerous theorems and conjectures: it is the smallest snark (a bridgeless cubic graph with chromatic index 4), the unique Moore graph of diameter 2 and degree 3, and a counterexample in Tait coloring problems related to the four-color theorem.^[1] Its spectrum is (-2)^4 1^5 3^1, and it admits a 6-coloring of the projective plane, highlighting its applications in combinatorial design and symmetry studies.^[1] Due to these attributes, it remains a cornerstone in graph theory education and research, often visualized as an outer pentagon connected to an inner star via spokes.^[1]

Introduction and History

Definition

The Petersen graph is an undirected simple graph consisting of 10 vertices and 15 edges.^[2] It is 3-regular, or cubic, with each vertex incident to exactly three edges.^[1] As a simple graph, it contains no loops or multiple edges between the same pair of vertices.^[2] The graph has girth 5, meaning its shortest cycles are of length 5 and it is free of triangles or quadrilaterals.^[1] One standard way to label its vertices is to identify them with the 2-element subsets of the set {1,2,3,4,5}, so there are \binom{5}{2} = 10 vertices; two vertices are adjacent if and only if the corresponding subsets are disjoint.^[3] It is named after the Danish mathematician Julius Petersen, who first described it in 1898.^[2] The Petersen graph is often depicted as an outer pentagon, with corresponding vertices of an inner pentagram connected by five radial edges, though this is merely a visualization and not a construction method.^[2]

Historical Background

The Petersen graph was implicitly described in 1886 by Alfred Kempe in connection with the Desargues configuration, where its vertices represent the ten lines and edges connect pairs of non-incident lines.^[1] It was introduced by Danish mathematician Julius Petersen in 1898 as a counterexample in his short paper "Sur le théorème de Tait," published in L'Intermédiaire des Mathématiciens, where he demonstrated that not every bridgeless cubic graph admits a three-edge-coloring, refuting a conjecture posed by P. G. Tait in 1878 regarding the edge-colorability of such graphs.^[4] Although Petersen provided a verbal description of the graph—defined as having 10 vertices and 15 edges, with specific connectivity properties—he did not include an explicit drawing.^[5] Kempe included an explicit drawing of the graph in his 1886 paper, while the first detailed study appeared in Dénes Kőnig's seminal 1936 textbook Theorie der endlichen und unendlichen Graphen, which marked a significant milestone in the formalization of graph theory and highlighted the graph's structural properties. The graph is non-Hamiltonian (a property proven in the mid-20th century) and serves as a counterexample to the broader hypothesis that all bridgeless cubic graphs are Hamiltonian, influencing developments beyond Tait's focus on polyhedral graphs.^[4] During the 1950s and 1960s, amid the resurgence of graph theory led by figures like Frank Harary and William Tutte, the Petersen graph gained widespread recognition as a prototypical non-planar graph and the smallest example of what would later be termed a snark—a bridgeless cubic graph requiring four colors for edge-coloring. Its enduring significance is evident in its inclusion in foundational textbooks from the 1960s onward, such as Harary's Graph Theory (1969), with no substantial historical developments or reinterpretations emerging after 2000.

Constructions and Representations

Combinatorial Constructions

The Petersen graph can be constructed as the complement of the line graph of the complete graph K_5. The graph K_5 has \binom{5}{2} = 10 edges, so its line graph L(K_5) has 10 vertices, each corresponding to an edge of K_5, with two vertices adjacent in L(K_5) if the corresponding edges share a vertex in K_5. In the complement \overline{L(K_5)}, edges connect vertices whose corresponding edges in K_5 are disjoint; since each edge in K_5 is disjoint from exactly three others (those not incident to its endpoints), the resulting graph is 3-regular with 10 vertices and $10 \times 3 / 2 = 15 edges.^[6] Another combinatorial construction identifies the Petersen graph with the Kneser graph KG(5,2), where the vertices are the 2-element subsets of the set \{1,2,3,4,5\}, of which there are \binom{5}{2} = 10, and two vertices are adjacent if the corresponding subsets are disjoint. For a fixed 2-subset, the number of disjoint 2-subsets from the remaining three elements is \binom{3}{2} = 3, yielding a 3-regular graph with 15 edges.^[7] The Petersen graph is equivalently the odd graph O_3, defined for k \geq 2 as the Kneser graph KG(2k-1, k-1), so O_3 = KG(5,2); its vertices represent the (3-1)-subsets of a (2 \cdot 3 - 1)-set, with edges between disjoint subsets.^[8] It also arises as the generalized Petersen graph G(5,2), constructed with 10 vertices partitioned into an outer 5-cycle and an inner 5-cycle; the outer vertices form a cycle graph C_5, each outer vertex connects to a corresponding inner vertex, and the inner vertices connect in a cycle shifted by two steps (i.e., each to the one two positions ahead). This yields a 3-regular graph with 15 edges.^[9] These constructions can be verified via the adjacency matrix, a $10 \times 10 symmetric matrix with zeros on the diagonal and exactly three 1's per row (off-diagonal), totaling 15 edges, matching the parameters derived from each build.

Geometric and Algebraic Representations

The Petersen graph is commonly visualized in a symmetric drawing featuring an outer 5-cycle representing five vertices, connected by five radial edges (spokes) to five inner vertices arranged in a pentagram (a 5-pointed star), where the inner vertices are linked by the star's edges but with no additional connections between adjacent inner vertices in the cyclic order.^[10] This representation highlights the graph's 3-regular structure and girth of 5, making it a canonical illustration in graph theory texts.^[11] Geometrically, the Petersen graph serves as the 1-skeleton of the hemi-dodecahedron, a non-orientable polyhedron obtained as the quotient of the dodecahedron by central inversion, resulting in a map on the real projective plane with 6 pentagonal faces, 15 edges, and 10 vertices.^[12] This polyhedral realization underscores its role in combinatorial geometry and abstract polytopes, where the hemi-dodecahedron's Petrie polygons correspond to the graph's cycles.^[13] Additionally, the graph admits a unit distance embedding in the Euclidean plane, where all edges are realized as segments of length 1, positioning it among unit distance graphs despite its non-planarity.^[14] It also arises as the derived graph from a voltage assignment on a base graph, for instance, using the cyclic group \mathbb{Z}_5 on a cycle with appropriate voltages to lift to the full structure.^[15] In the Foster census of symmetric cubic graphs, the Petersen graph appears as the unique (3,5)-cage graph, cataloged as the smallest 3-regular graph of girth 5 and serving as a benchmark for enumerating symmetric trivalent graphs up to 512 vertices.^[16]

Embeddings and Planarity

Planarity and Crossing Number

The Petersen graph is non-planar, as it contains a subdivision of K_{3,3}, the complete bipartite graph on two parts of three vertices each. By Kuratowski's theorem, a finite graph is planar if and only if it contains no subdivision of K_5 or K_{3,3} as a subgraph; the presence of such a subdivision in the Petersen graph thus certifies its non-planarity.^[17] Specifically, one such subdivision can be identified by partitioning the vertices into two sets of five (corresponding to the outer pentagon and inner star in the standard drawing) and selecting paths that connect them without forming a K_{3,3} subgraph directly, but subdividing edges to match the structure.^[18] An alternative proof of non-planarity relies on Euler's formula for connected planar graphs, v - e + f = 2, where v is the number of vertices, e the number of edges, and f the number of faces (including the outer face), combined with the graph's girth of 5. Since every face in a planar embedding must bound at least 5 edges and each edge bounds at most 2 faces, it follows that $2e \geq 5f. Substituting into Euler's formula yields f \leq \frac{2e}{5}, so v - e + \frac{2e}{5} \leq 2, or e \leq \frac{5}{3}(v - 2). For the Petersen graph with v = 10 and e = 15, \frac{5}{3}(10 - 2) = \frac{40}{3} \approx 13.33, so e \leq 13; the contradiction $15 > 13 confirms non-planarity.^[19] This bound generalizes the standard e \leq 3v - 6 for simple planar graphs (girth at least 3) and highlights the role of the Petersen graph's high girth in tightening the inequality. Although non-planar, the Petersen graph has crossing number 2, the smallest number of edge crossings required in any drawing in the plane. A drawing achieving exactly 2 crossings exists, for instance, by placing the outer pentagon and connecting to the inner vertices with minimal overlaps, as in the standard representation where two edges cross in the interior. To show that 1 crossing is impossible, consider that any drawing with at most 1 crossing would imply a near-planar structure, but direct enumeration or bounds like cr(G) \geq \frac{e^3}{64v^2} (the crossing lemma) yield cr \geq \frac{15^3}{64 \times 10^2} = \frac{3375}{6400} \approx 0.53, which is weak; stronger arguments use the fact that removing edges to eliminate crossings disconnects the graph or violates connectivity, confirming the minimum is 2.^[20] The non-planarity of the Petersen graph serves as a key example in graph coloring theory, particularly in relation to the four color theorem, which asserts that every planar graph is 4-vertex-colorable. As a non-planar graph that is 3-vertex-colorable, the Petersen graph does not contradict the theorem, since the theorem's hypothesis restricts it to planar graphs; instead, it underscores that non-planar graphs may admit colorings with fewer than 4 colors while still requiring careful embedding analysis.^[19]

Embeddings on Surfaces

The Petersen graph cannot be embedded on the sphere, as established by its non-planarity. Its minimal genus is 1, allowing embeddings on both the torus (orientable genus 1) and the projective plane (non-orientable genus 1). These embeddings are cellular, with faces homeomorphic to open disks, and represent the smallest surfaces on which the graph can be drawn without crossings.^[21]^[22] On the projective plane, the Petersen graph realizes the hemi-dodecahedron, a regular abstract polyhedron of type {5,3}₅ with 10 vertices, 15 edges, and 6 pentagonal faces. This embedding identifies opposite points on the boundary of a disk representation, resulting in a symmetric configuration where the graph's structure aligns with the polyhedron's skeleton. The dual of this embedding is the complete graph K₆, which has chromatic number 6; consequently, the faces of the hemi-dodecahedral map require 6 colors, establishing a lower bound for the chromatic number of the projective plane.^[23]^[24] The torus embedding similarly features 6 faces, supporting studies in surface map colorings, though the projective plane realization is particularly notable for its connection to polyhedral models and chromatic bounds.^[21]

Symmetries and Automorphism Group

Automorphism Group

The automorphism group of the Petersen graph is isomorphic to the symmetric group S_5 on five elements, which has order $5! = 120.^[25] This group acts faithfully on the graph, preserving its structure as a 3-regular graph on 10 vertices.^[26] In the Kneser graph construction of the Petersen graph, the vertices correspond to the 2-element subsets of a 5-element set, with edges between disjoint subsets; permutations in S_5 act naturally on these subsets, inducing graph automorphisms that generate the full group.^[26] The order of the automorphism group can be computed using the orbit-stabilizer theorem: S_5 acts transitively on the 10 vertices, and the stabilizer of a fixed vertex (a 2-subset) consists of permutations fixing that subset setwise, which has order 12 (isomorphic to S_2 \times S_3), yielding |Aut(G)| = 10 \times 12 = 120. The outer automorphism group of S_5 is trivial, meaning all automorphisms of the automorphism group of the Petersen graph are inner. In the standard drawing of the Petersen graph as an outer pentagon connected to an inner pentagram, a subgroup of order 10, isomorphic to the dihedral group D_5, is generated by rotations and reflections of the pentagonal symmetry.^[10]

Transitivity and Regularity Properties

The Petersen graph is vertex-transitive, as its automorphism group acts transitively on the set of vertices, ensuring that all vertices are symmetric and possess isomorphic neighborhoods. It is also edge-transitive, meaning any edge can be mapped to any other edge via an automorphism, which reflects the uniformity in the graph's edge structure. Moreover, the graph is arc-transitive, with the automorphism group acting transitively on ordered pairs of adjacent vertices (arcs); in fact, it is 3-arc-transitive, allowing transitivity on sequences of three consecutive arcs, but not 4-arc-transitive. These transitivity properties extend to distances, making the Petersen graph distance-transitive with a diameter of 2. This implies that the automorphism group acts transitively on pairs of vertices at the same distance, so all pairs at distance 1 (adjacent vertices) and distance 2 (non-adjacent vertices) are equivalent under symmetry, facilitating uniform geometric interpretations across the graph. The Petersen graph is strongly regular with parameters (10, 3, 0, 1), denoted as srg(10, 3, 0, 1). In this context, the parameters indicate that it has 10 vertices, each of degree 3, with λ = 0 (any two adjacent vertices share no common neighbors) and μ = 1 (any two non-adjacent vertices share exactly one common neighbor). These parameters underscore the graph's regularity and the precise symmetry in neighbor intersections, which aligns with its transitivity properties by ensuring consistent local structures throughout the graph.

Paths, Cycles, and Connectivity

Hamiltonian Paths and Cycles

The Petersen graph does not contain a Hamiltonian cycle. This non-Hamiltonicity can be proven by contradiction using the graph's girth of 5: assuming a 10-cycle exists leads to the presence of a shorter cycle, which contradicts the girth property.^[27] An elegant case analysis confirms this result, showing that no such cycle can traverse all 10 vertices without violating structural constraints.^[28] The Petersen graph served as the first counterexample to the conjecture that every 3-connected cubic graph is Hamiltonian, highlighting the challenges in determining Hamiltonicity for such graphs.^[29] Despite the absence of Hamiltonian cycles, the Petersen graph admits Hamiltonian paths. In particular, it is maximally non-Hamiltonian in the sense that a Hamiltonian path exists between any pair of non-adjacent vertices, ensuring high connectivity via paths despite the cycle deficiency.^[30] The total number of undirected Hamiltonian paths is 120, a figure tied to the order of the graph's automorphism group.^[1] The Petersen graph is also hypohamiltonian: it lacks a Hamiltonian cycle, but the subgraph obtained by removing any single vertex is Hamiltonian. This property was established through exhaustive verification of the resulting 9-vertex subgraphs.^[31] Such subgraphs admit cycles spanning their vertices, underscoring the graph's delicate balance between non-Hamiltonicity and near-Hamiltonicity.

Girth, Cycles, and Connectivity

The Petersen graph has girth 5, the length of its shortest cycle, which implies that it contains no triangles or 4-cycles.^[1] This property makes it a valuable counterexample in graph theory for problems involving short cycles. As the unique (3,5)-cage graph, it is the smallest 3-regular graph achieving this girth, with 10 vertices and 15 edges.^[1] The graph features 12 distinct 5-cycles and 10 distinct 6-cycles, highlighting its rich but limited short-cycle structure beyond the girth.^[32]^[33] These cycles contribute to its non-bipartite nature, as the odd-length 5-cycles prevent a 2-coloring of the vertices. The Petersen graph is 3-vertex-connected and 3-edge-connected, matching its regularity.^[1] Vertex connectivity of 3 follows from Menger's theorem, ensuring at least three vertex-disjoint paths between any pair of non-adjacent vertices, while the absence of bridges confirms the edge connectivity.^[1] The cycle space of the Petersen graph, consisting of all even-degree subgraphs (Eulerian subgraphs), has dimension 6, computed as the cyclomatic number |E| - |V| + 1 = 15 - 10 + 1.^[34] A basis for this vector space over GF(2) can be constructed from six linearly independent cycles, such as a fundamental set relative to a spanning tree, spanning all even subgraphs including the 5-cycles and 6-cycles.^[34]

Coloring Properties

Vertex Coloring

The Petersen graph has chromatic number 3, as it requires three colors for a proper vertex coloring in which no two adjacent vertices share the same color, but cannot be colored with fewer.^[1] This follows from the presence of odd-length cycles, including cycles of length 5, which prevent a 2-coloring.^[1] In an optimal 3-coloring, the 10 vertices are partitioned into three independent sets of sizes 4, 3, and 3.^[35] There are exactly 20 such colorings up to permutation of the colors, reflecting the graph's high symmetry.^[33] As a triangle-free graph (with girth 5) that is 3-chromatic, the Petersen graph illustrates the necessity of the planarity condition in Grötzsch's theorem, which asserts that every triangle-free planar graph is 3-colorable.^[1] The list chromatic number of the Petersen graph is also 3, meaning that if each vertex is assigned a list of three colors, there exists a proper coloring where each vertex receives a color from its list.^[36]

Edge Coloring

The Petersen graph is a 3-regular simple graph, so by Vizing's theorem its edge chromatic number \chi' satisfies \Delta \leq \chi' \leq \Delta + 1, where \Delta = 3. It has been established that \chi' = 4, classifying it as a Class II graph.^[37] This means no proper edge coloring exists using only 3 colors, despite the graph's regularity suggesting a possible 1-factorization. As the unique smallest (10-vertex) example of a cyclically 4-edge-connected, bridgeless cubic graph with \chi' = 4, the Petersen graph is the prototypical snark. Snarks, introduced in the context of counterexamples to Tait's conjecture on 3-edge-colorability of cubic planar graphs, highlight the distinction between Class I and Class II behaviors in cubic graphs. The Petersen graph's resistance to 3-edge-coloring, often termed a failure of Tait coloring, underscores its role in disproving early assumptions about uniform edge colorability for non-planar cubics. A proper 4-edge-coloring of the Petersen graph partitions its 15 edges into four matchings, where each matching is a set of vertex-disjoint edges.^[37] Since the graph has 10 vertices, each matching covers at most 5 edges, and in a minimal such partitioning, the matchings collectively saturate all vertices while avoiding conflicts. This partitioning is essential for applications in scheduling and network design where edge-disjoint paths are required.

Algebraic and Metric Properties

Spectrum and Eigenvalues

The spectrum of the adjacency matrix of the Petersen graph consists of the eigenvalue $3

with multiplicity &#36;1

, the eigenvalue $1

with multiplicity &#36;5

, and the eigenvalue -2 with multiplicity $4$. This spectrum arises from the graph's strongly regular parameters and can be derived using the formula for eigenvalues of strongly regular graphs. The characteristic polynomial of the adjacency matrix is (\lambda - 3)(\lambda - 1)^5(\lambda + 2)^4.^[38] The Laplacian spectrum of the Petersen graph, derived from the adjacency spectrum since the graph is $3

-regular, consists of the eigenvalue &#36;0

with multiplicity $1

, the eigenvalue &#36;2

with multiplicity $5

, and the eigenvalue &#36;5

with multiplicity $4$. These spectral properties position the Petersen graph as a Ramanujan graph, where the absolute values of the nontrivial adjacency eigenvalues satisfy |\lambda_i| \leq 2\sqrt{d-1} = 2\sqrt{2} \approx 2.828 for degree d=3, achieving the Alon-Boppana bound and indicating near-optimal expander behavior.^[38]

Distance, Diameter, and Strongly Regular Parameters

The Petersen graph has a diameter of 2, meaning the longest shortest path between any two vertices is of length 2.^[1] This property arises because the graph is connected and every pair of non-adjacent vertices shares exactly one common neighbor, ensuring no vertex pair requires more than two edges to connect.^[1] Similarly, the radius of the Petersen graph is 2, indicating that the maximum eccentricity (the greatest distance from any vertex to another) is 2, and thus every vertex can reach all others in at most two steps.^[1] For each vertex, there are 3 neighbors at distance 1 and 6 vertices at distance 2, confirming this metric uniformity due to the graph's vertex-transitivity.^[1] The Petersen graph is strongly regular with parameters (n,k,\lambda,\mu)=(10,3,0,1), where n=10 is the number of vertices, k=3 is the degree of each vertex, \lambda=0 means any two adjacent vertices have no common neighbors, and \mu=1 means any two non-adjacent vertices have exactly one common neighbor.^[1] These parameters satisfy the standard strongly regular equations, including the adjacency count relation k(k-\lambda-1)=\mu(n-k-1), which here yields $3(3-0-1)=1(10-3-1) or $6=6, verifying the graph's regularity in neighbor intersections. The Wiener index of the Petersen graph, defined as the sum of shortest-path distances over all unordered pairs of vertices, is 75.^[39] This value reflects the graph's compact metric structure, with the total distance sum computed as half the sum over all vertices of the distances from that vertex to all others: $10 \times 15 / 2 = 75, where the sum of distances from each vertex is $3 \times 1 + 6 \times 2 = 15.^[39]

Conjectures Involving the Petersen Graph

Petersen Coloring Conjecture

The Petersen coloring conjecture, proposed by François Jaeger in 1985, posits that every bridgeless cubic graph admits a proper 5-edge-coloring with no abnormal edges, where an abnormal edge is one for which the set of colors on the edges adjacent to its endpoints has exactly three distinct colors.^[40] An equivalent statement, also due to Jaeger, asserts that every bridgeless cubic graph G has a mapping from its edges to the edges of the Petersen graph P such that for every vertex v in G, the images of the edges incident to v form the entire neighborhood of some vertex in P.^[41] This edge-mapping preserves adjacency in a strong sense, effectively embedding the cycle space properties of P into G. The conjecture ties directly to the cycle double cover problem: if true, it implies that every bridgeless cubic graph possesses a cycle double cover, where every edge lies in exactly two cycles, as the mapping induces such a covering via the cycles in P.^[42] The conjecture remains open as of 2025, with no counterexamples known despite extensive computational checks on small graphs and specific families.^[43] It has been verified for numerous classes, including all planar cubic bridgeless graphs (via the four color theorem and extensions), graphs with maximum degree at most four, and many snark families—non-3-edge-colorable cubic bridgeless graphs that serve as minimal counterexamples to related conjectures.^[40] For instance, it holds for flower snarks and Loupekhine snarks, key examples in snark theory, supporting its consistency with the broader landscape of cubic graph colorings.^[44] Partial progress includes results showing that every bridgeless cubic graph has a 5-edge-coloring where at least one-third of the edges are normal (non-abnormal), and stronger approximations for specific structures like near-bipartite graphs.^[41] Historically, Jaeger introduced the conjecture in the context of nowhere-zero flows and edge-colorings, building on earlier work linking the Petersen graph's non-3-edge-colorability to universal properties of cubic graphs; subsequent reformulations in terms of partial orders and flow-continuity have facilitated these advances.^[42] The conjecture's resolution would unify several open problems in graph theory, including implications for the snark theorem conjecturing that every snark contains the Petersen graph as a minor.^[40]

Hypohamiltonian and Snark Properties

The Petersen graph is hypohamiltonian, meaning it lacks a Hamiltonian cycle but becomes Hamiltonian upon the removal of any single vertex.^[45] This property was established in early studies of cubic graphs, confirming that every vertex-deleted subgraph contains a cycle passing through all remaining vertices.^[46] As the unique hypohamiltonian graph on 10 vertices, the Petersen graph serves as the smallest example of this class, highlighting its role in exploring the boundaries between Hamiltonian and non-Hamiltonian structures in graph theory.^[1] The Petersen graph also holds a central position as the smallest snark, defined as a cyclically 4-edge-connected cubic graph with chromatic index 4, meaning its edges cannot be colored with only three colors such that no two adjacent edges share the same color.^[47] Introduced in the context of Tait's 1880s attempts to prove the four-color theorem via edge colorings of planar cubic graphs, the Petersen graph provided a non-planar counterexample that disrupted these efforts, as no snarks exist on fewer than 10 vertices.^[48] All snarks, including the Petersen graph, are non-Hamiltonian; a Hamiltonian cycle in a cubic snark would allow a 3-edge-coloring by alternating two colors along the cycle and using a third for the remaining perfect matching, contradicting the definition.^[47] In relation to the cycle double cover conjecture, proposed by Tutte in the 1970s, which asserts that every bridgeless graph admits a cycle double cover—a collection of cycles where each edge appears exactly twice—the Petersen graph plays a key role as a minimal counterexample to weaker variants.^[49] While it possesses a cycle double cover consisting of exactly five cycles, it lacks one with four or fewer, equivalent to the absence of a nowhere-zero 4-flow. This underscores the Petersen graph's implications for the 5-cycle double cover conjecture, which posits that every bridgeless graph has such a cover with at most five cycles and remains open, with the Petersen graph achieving the bound.^[49] The Desargues graph is a 20-vertex cubic graph that serves as the bipartite double cover of the Petersen graph, obtained by replacing each vertex of the Petersen graph with a pair of vertices and each edge with a matching between the pairs.^[50] It is also isomorphic to the generalized Petersen graph G(10,3), highlighting its structural similarity to the Petersen graph G(5,2).^[51] The Hoffman-Singleton graph is a 50-vertex 7-regular graph that acts as a higher-degree analog to the Petersen graph within the cage problem, as both are Moore graphs achieving the theoretical minimum number of vertices for their respective degrees and girth of 5—the Petersen as the unique (3,5)-cage and the Hoffman-Singleton as the unique (7,5)-cage.^[52] Generalized Petersen graphs form a family G(n,k) constructed by taking an outer n-cycle, an inner star of n vertices each connected to two nonconsecutive outer vertices via parameter k (with $1 \leq k < n/2 and \gcd(n,k)=1), and the Petersen graph specifically realizes G(5,2).^[53] This family generalizes the symmetric and cage-like properties of the Petersen graph, with many members exhibiting high symmetry or hypohamiltonian traits.^[54] The Petersen graph is isomorphic to the complement of the line graph of the complete graph K_5, where the line graph L(K_5) has vertices corresponding to the 10 edges of K_5 and edges between vertices if the corresponding edges in K_5 share a vertex, making the complement connect non-adjacent edges.^[55] Flower snarks constitute an infinite family of cyclically 4-edge-connected cubic snarks, with the smallest member J_3 being isomorphic to the Petersen graph, and larger J_n (for odd n \geq 5) constructed by replacing cycles in a Petersen-like structure with alternating spoke and hub connections to generalize its snark properties such as class II edge-coloring and non-3-edge-colorability.^[56]

Applications in Graph Theory

The Petersen graph serves as a foundational counterexample in graph theory, illustrating that not every 3-connected cubic graph is Hamiltonian.^[29] Tait conjectured in the late 19th century that every 3-connected planar cubic graph is Hamiltonian; the Petersen graph, though non-planar, provides an early example of a non-Hamiltonian 3-connected cubic graph, with its non-Hamiltonicity—established through case analysis showing no cycle visits all 10 vertices—disproving the conjecture without the planarity condition.^[57] In the cage problem, which seeks the smallest regular graph of given degree and girth, the Petersen graph is the unique (3,5)-cage: the minimal 3-regular graph with girth 5, having exactly 10 vertices as predicted by the Moore bound for these parameters.^[1] This role highlights its extremal properties and influences constructions of larger cages. As the smallest snark—a bridgeless cubic graph requiring four colors for edge coloring (chromatic index 4)—the Petersen graph motivated the systematic study of snarks and related problems, including Tutte's conjecture that every snark contains the Petersen graph as a minor, announced in 1999 by Robertson, Sanders, Seymour, and Thomas.^[47]) In algebraic graph theory, the Petersen graph exemplifies a strongly regular graph with parameters (10,3,0,1), where each vertex has degree 3, adjacent vertices share no common neighbors (λ=0), and non-adjacent vertices share exactly one (μ=1); its spectrum, with eigenvalues 3 (multiplicity 1), 1 (multiplicity 5), and -2 (multiplicity 4), aids in demonstrating theorems on eigenvalues and expanders. More recently, the Petersen graph underlies constructions in error-correcting codes, notably the [15,6,5] Petersen cycle code, derived from its incidence matrix, which corrects up to two errors by leveraging its metric properties.^[58]

References

[1]
Petersen Graph -- from Wolfram MathWorld
The Petersen graph is the cubic graph on 10 vertices and 15 edges which is the unique (3,5)-cage graph (Harary 1994, p. 175), as well as the unique (3 ...
[2]
The Petersen Graph - Cambridge University Press & Assessment
This Book has been cited by the following publications. This list is generated based on data provided by Crossref. ; Online publication date: March 2010 ; Print ...
[3]
[PDF] arXiv:1609.08072v1 [math.CO] 26 Sep 2016
Sep 26, 2016 · A formal description of the Petersen graph runs as follows: the vertices are the 2- element subsets of a 5-element set, and edges represent the ...
[4]
Julius Petersen's theory of regular graphs - ScienceDirect.com
Petersen. Die Theorie der regulären graphs. Acta Math., 15 (1891), pp. 193-220. Crossref View in Scopus Google Scholar. [23]. J. Petersen. Sur le théorème de ...
[5]
Julius Petersen (1839 - 1910) - Biography - MacTutor
In 1891 Julius Petersen published a paper that contained his now famous theorem: any bridgeless cubic graph has a 1-factor. These days Petersen's theorem is ...Missing: original citation
[6]
[PDF] Graph Theory - Lecture notes. - Indian Statistical Institute, Bangalore
Apr 28, 2019 · Exercise 3.1.12. Show that the Petersen graph is the complement of the line graph of K5. Exercise 3.1.13. Are the following three graphs ...
[7]
Kneser Graph -- from Wolfram MathWorld
The Kneser graphs are a class of graph introduced by Lovász (1978) to prove Kneser's conjecture. Given two positive integers n and k, the Kneser graph K(n,k), ...Missing: constructions line
[8]
https://www.combinatorics.org/ojs/index.php/eljc/article/download/DS22/pdf
[9]
Generalized Petersen Graph -- from Wolfram MathWorld
The generalized Petersen graph is cubic, m/n=3/2, where m is the edge count and n is the vertex count. More specifically, GP(n,k) has 2n nodes and 3n edges.
[10]
[PDF] Section 1.2. Isomorphisms and Automorphisms
May 18, 2022 · of the Petersen graph; that is, the Petersen graph is vertex ... outer pentagon is similar to at least one of the vertices of the inner ...
[11]
[PDF] Part I. Graph Theory 3 Part II. Balance and Imbalance 8 ... - People
Deservedly a favorite in graph theory, the Petersen graph P illustrates many of the im- portant properties of graphs, either as a non-trivial example or, ...
[12]
[PDF] Combinatorics of embeddings
4-sphere whose 1-skeleton is the Petersen graph. ... is the Petersen graph, then Kξ can be chosen to ... ular, by the hemi-dodecahedron Pξ. Remark 4.13 ...
[13]
[PDF] Groups represented by incidence geometries - arXiv
Jun 12, 2025 · The graph G obtained as the {0,1}-truncation of Γ (the 1-skeleton) is the Petersen graph. ... hemidodecahedron is self-Petrie dual; it is ...
[14]
https://arxiv.org/pdf/0711.1157
[15]
[PDF] Beyond symmetry in generalized Petersen graphs - UB
In this section we study generalized Petersen graphs that are underlying graphs of Cayley graphs of semigroups or monoids. Let us start with four semigroup ...
[16]
[PDF] Applications Of Ordinary Voltage Graph Theory To Graph ...
Keywords: voltage graph, cellular automorphism, Generalized Petersen Graph. 1 Introduction. An ordinary voltage graph encodes a highly symmetric covering ...
[17]
[PDF] The spectrum of an I-graph
The class of I-graphs was introduced in the Foster Census [4] as a nat- ... The. Petersen graph is I(5,1,2). The class of I ... of eigenvalues of arbitrary cubic ...
[18]
[PDF] Section 10.5. Kuratowski's Theorem
Apr 6, 2023 · The Petersen graph behaves similarly in that it has a K5-minor graph but no K5- subdivision; it has a K3,3-subdivision but not a K3,3 subgraph ( ...
[19]
[PDF] Lecture 21: Planarity testing 1 Triangulations - Faculty Web Pages
Oct 24, 2024 · Here is a subdivision of K3,3 inside the Petersen graph: By Kuratowski's theorem, the Petersen graph is not planar. 4. Page 5. Okay, but how ...
[20]
[PDF] GRAPH THEORY WITH APPLICATIONS
This book is intended as an introduction to graph theory. Our aim has been to present what we consider to be the basic material, together with a wide.
[21]
[PDF] Crossing Number of a Graph from Interactive Mathematics ...
May 27, 2008 · For the Petersen graph, c = 5. (Looking at the leftmost avitar in the upper row above, the outer pentagon and the inner star are 5-cycles. Other ...
[22]
The genus of Petersen powers - Mohar - 2011 - Wiley Online Library
Oct 26, 2010 · We show that the Petersen graph is the only Petersen power which embeds into the projective plane. Both Blanuša snarks have non-orientable genus ...
[23]
[PDF] Section 10.6. Surface Embeddings of Graphs
Apr 30, 2021 · Surface embeddings extend planar embeddings to surfaces other than the plane. Surfaces are classified as orientable or nonorientable, and are 2 ...
[24]
[PDF] Polyhedral Models of the Projective Plane - The Bridges Archive
The hemi-dodecahedron is particularly interesting. Its edges are those of the Petersen graph, the usual representation of which suggests an obvious way to ...
[25]
[PDF] Chapter 15. Colourings of Maps
Aug 26, 2022 · In Figure 25(a) we have an embedding of K6 on the projective plane, establishing 6 as the chromatic value of the projective plane ...
[26]
The groups of the generalized Petersen graphs
Oct 24, 2008 · Roberto Frucht ,. Jack E. Graver and. Mark E. Watkins. Show author ... (8)Watkins, Mark E.A Theorem on Tait colorings with an application ...
[27]
https://dwest.web.illinois.edu/igt/igt2comm.html
[28]
Full article: Involutive automorphism of symmetric groups
If n≠2 or n≠6, then every automorphism of 𝒮n is inner. If 𝜃 is an outer automorphism of 𝒮6, and if τ∈𝒮6 is a transposition, then 𝜃(τ) is ...
[29]
"Introduction to Graph Theory - comments" - Douglas West's
1.40 will be followed by this short proof that the Petersen graph has no 10-cycle, using girth 5: "If there is a 10-cycle C, then the graph consists of C plus ...
[30]
[PDF] Chapter 18. Hamilton Cycles
Dec 7, 2022 · The Petersen graph is nonhamiltonian (by Exercise 17.1.8), but Bondy and. Murty state (see page 479) that this cannot be deduced from Theorem ...
[31]
[PDF] Cuts in matchings of 3-connected cubic graphs
Sep 5, 2018 · Every 3-connected, cubic, planar graph contains a Hamiltonian cycle. ... The first counterexample to this statement is the Petersen graph.<|control11|><|separator|>
[32]
(PDF) Hamiltonian Paths in Non-Hamiltonian Graphs - ResearchGate
Jul 31, 2025 · ... Petersen graph, P(see Figure 1). The Petersen graph has no Hamiltonian. cycles, but has a Hamiltonian path between any two non-adjacent vertices ...<|control11|><|separator|>
[33]
[PDF] Small Hypohamiltonian Graphs
The solution, due to Gaudin, Herz and Rossi [5] established that the Petersen graph is the smallest hypohamiltonian graph. Since that time Herz. Duby and ...
[34]
Hadwiger's Conjecture and inflations of the Petersen graph
The Petersen graph is triangle-free but contains 12 distinct 5-cycles. ... 2 contains no other odd cycles than 5-cycles; the independence number of ≔ ...
[35]
[PDF] On the maximum number of cycles in a graph - OEIS
) = 15 with nine 4-cycles and six 6-cycles; and if. Y (P) is the Petersen graph, then. 6-cycles, fifteen 8-cycles and twenty 9-cycles. = 57 from twelve 5 ...
[36]
[PDF] Minimum Cycle Bases and Their Applications - mediaTUM
Cycle bases (in bold) of an orientation of the Petersen graph (with unit edge- weights); the cycle spaces over Q and GF(2) have dimension µ = 15 − 10 + 1 = 6.
[37]
Full article: On the local distinguishing chromatic number
We consider the color classes of common coloring with 3 colors. Next we show that the number of elements of color classes, and , are 4, 3 and 3, respectively.<|control11|><|separator|>
[38]
Petersen graph
Julius Petersen (1839-1910) was a Danish mathematician. Around 1898 he constructed the graph bearing his name as the smallest counterexample.Missing: original paper<|control11|><|separator|>
[39]
[PDF] On List-Coloring and the Sum List Chromatic Number of Graphs.
Brooks' Theorem for the chromatic number of a graph is an excellent example of constructing a vertex ordering and applying the algorithm, but a more relevant ...
[40]
The circular chromatic index - ScienceDirect.com
In the next theorem we show that the circular chromatic index of the Petersen graph is smaller than its chromatic index. Theorem 6. If G is the Petersen graph ...
[41]
[PDF] Ramanujan Graphs - Department of Mathematics and Statistics
The Petersen graph (see Figure 1) is a 3-regular graph whose adjacency matrix has characteristic polynomial (λ − 3)(λ + 2)4(λ − 1)5, and thus is easily seen to ...
[42]
A Relation between D-Index and Wiener Index for r‐Regular Graphs
Feb 22, 2020 · Let G be a Petersen graph of ten orders, as shown in Figure 1. It is clear that W(PT10) = 75, then . Description unavailable. Figure 1. Open ...<|control11|><|separator|>
[43]
[1905.07913] Variations on the Petersen colouring conjecture - arXiv
May 20, 2019 · The Petersen colouring conjecture states that every bridgeless cubic graph admits an edge-colouring with 5 colours such that for every edge e, ...Missing: Thomason | Show results with:Thomason
[44]
https://arxiv.org/abs/2306.13340
[45]
[PDF] Variations on the Petersen colouring conjecture - HAL
Dec 7, 2020 · [9] F. Jaeger, On five-edge-colorings of cubic graphs and nowhere-zero flow problems, Ars Combin. 20. (1985), no. B, 229–244. [10] D. Král ...
[46]
https://doi.org/10.1002/jgt.22043
[47]
Normal 5-edge-coloring of some snarks superpositioned by Flower ...
Jun 23, 2023 · The Petersen Coloring Conjecture is equivalent to stating that every bridgeless cubic graph has a normal 5-edge-coloring. Since every 3-edge ...
[48]
Hypohamiltonian Graph -- from Wolfram MathWorld
61). The Petersen graph, which has ten nodes, is the smallest hypohamiltonian graph ... girth-restricted subset of cubic hypohamiltonian up to 26 vertices.
[49]
Hypohamiltonian Planar Cubic Graphs with Girth 5 - McKay - 2017
Apr 19, 2016 · A graph is called hypohamiltonian if it is not hamiltonian but becomes hamiltonian if any vertex is removed. Such graphs exist on orders 10 (the ...
[50]
Snark -- from Wolfram MathWorld
The Petersen graph is the smallest snark, and Tutte conjectured that all snarks have Petersen graph graph minors. This conjecture was proven in 2001 by ...
[51]
Note Recognizing generalized Petersen graphs in linear time
Sep 15, 2020 · In this paper we give a linear-time recognition algorithm for the family of generalized Petersen graphs. In particular, we identify a local property which ...
[52]
[PDF] A survey of the cycle double cover conjecture - Brown Math
Jul 2, 2009 · A cycle double cover of a graph G is a list of cycles of G such that every edge of G appears exactly twice. The cycle double cover ...Missing: Thomason | Show results with:Thomason
[53]
[PDF] arXiv:1001.0674v2 [quant-ph] 20 Oct 2010
Oct 20, 2010 · The Desargues graph and its cospectral mate. The bipartite double cover of the Petersen graph is called Desargues graph. There are many ...Missing: sources | Show results with:sources
[54]
[PDF] Multiple Kronecker Covering Graphs - arXiv
May 8, 2005 · Figure 1: The Desargues graph G(10, 3) is a Kronecker cover of Petersen graph. G(5, 2) and of the graph X. Proof. By definition, the vertex ...
[55]
[PDF] Dynamic Cage Survey - The Electronic Journal of Combinatorics
The Petersen graph [94] is the (3,5)-cage and has order 10. It can be constructed as the complement of the line graph of K5, from which it follows that the ...
[56]
[PDF] The Petersen Graph and its Generalizations - IJFMR
Petersen, Die Theorie der regularen graphs, Acta Math. 15 (1891) 193-200. 2. P.G. Tait, Listing's Topologie, Phil. Mag. 17 (1884) 30-46. 3. J. Petersen ,Sur ...
[57]
[PDF] The spectrum of generalized Petersen graphs - ResearchGate
In this research we completely describe the spectrum for the class of graphs, defined below. The generalized Petersen graph (GPG) P(n, k) has vertices ...
[58]
[PDF] Graph Theory
Aug 31, 2014 · The Petersen graph is the complement of the line graph of K5. It is also the Kneser graph KG5,2; this means that it has one vertex for each 2- ...
[59]
[PDF] Morphology of small snarks - The Electronic Journal of Combinatorics
Dec 13, 2021 · The flower snark J3 arises from the Petersen graph by substituting a triangle for a vertex. For each k ! 2, the snark J2k+1 can be ...
[60]
Prove Petersen graph is not Hamiltonian using deduction and no ...
Feb 3, 2013 · The following elegant proof due to D. West demonstrates that the Petersen graph is non-Hamiltonian. If there is a 10−cycle C, then the graph ...Difficulty in understanding the proof of Petersen Graph is non ...Short proof for the non-Hamiltonicity of the Petersen GraphMore results from math.stackexchange.com
[61]
$[15,6,5]$ Petersen cycle code | Error Correction Zoo
A [ 15 , 6 , 5 ] cycle code whose parity-check matrix is the incidence matrix of the Petersen graph. The Petersen graph can be thought of as a dodecahedron with ...