The Petersen graph
Share
The Petersen graph is a small, highly symmetric graph that graph theorists use as a standard counterexample. It has 10 vertices and 15 edges. Every vertex has degree 3 (it is cubic, or 3-regular), the shortest cycle has length 5 (its girth is 5), and any two vertices are at most two edges apart (its diameter is 2).
It is named after Julius Petersen, who in 1898 published it as the smallest bridgeless cubic graph that cannot be 3-edge-coloured. The same graph had already appeared twelve years earlier, in an 1886 paper by A. B. Kempe, as the graph of the Desargues configuration. Donald Knuth later called it “a remarkable configuration that serves as a counterexample to many optimistic predictions about what might be true for graphs in general.”
That is why it shows up in courses. Once a statement has been checked on complete graphs, cycles and trees, the Petersen graph is often the next place it breaks.
A standard drawing
The usual picture is an outer pentagon, an inner pentagram, and five spokes. In the labelling below, the outer vertices are 0–4 (0 at the top, then clockwise), the inner vertices are 5–9, and each spoke joins i to i + 5. The inner star joins each inner vertex to the vertex two steps around the inner pentagon: 5–7–9–6–8–5.
networkx.petersen_graph().The five-pointed drawing has five crossings. The graph is nevertheless non-planar: it cannot be drawn in the plane with no crossings. Its crossing number is 2 — there are drawings with only two crossings, and none with fewer. It can be drawn without crossings on a torus, and also on the projective plane (it is the skeleton of the hemi-dodecahedron).
The pentagon-and-star picture is only one way to draw it. Mark Dominus's The many faces of the Petersen graph redraws it to show at a glance that its diameter is 2, and that it also has threefold, fourfold and sixfold symmetry, none of which you'd guess from the pentagon.
Facts
| Vertices | 10 |
|---|---|
| Edges | 15 |
| Regularity | 3-regular (cubic) |
| Girth | 5 |
| Diameter | 2 |
| Radius | 2 |
| Chromatic number χ(G) | 3 |
| Chromatic index χ′(G) | 4 |
| Fractional chromatic index | 3 |
| Automorphism group | S5, order 120 |
| Planar? | No. Crossing number 2 |
| Hamiltonian? | No Hamiltonian cycle; it does have a Hamiltonian path |
| Hypohamiltonian? | Yes — delete any vertex and a Hamiltonian cycle appears. It is the smallest hypohamiltonian graph |
| Connectivity | 3-connected, bridgeless |
| Strongly regular | srg(10, 3, 0, 1) |
| Kneser graph | KG(5, 2) |
| Generalized Petersen graph | G(5, 2) |
| Cage / Moore graph | Unique (3, 5)-cage; unique (3, 5)-Moore graph |
| Snark? | Yes — the smallest snark |
| Spectrum | 3, 15, −24 (an integral graph) |
| Characteristic polynomial | (t − 1)5 (t + 2)4 (t − 3) |
| Independence number | 4 |
| Domination number | 3 |
| Perfect matchings | 6 |
| Spanning trees | 2,000 (the most of any 10-vertex cubic graph) |
| Cayley graph? | No. It is the smallest connected vertex-transitive graph that is not a Cayley graph |
A few of those rows are doing a lot of work, and they are the ones that tend to appear in lectures.
Why it is a counterexample
It is not Hamiltonian. There is a path through every vertex, but no cycle that visits every vertex once and returns. Among bridgeless cubic graphs, it is the smallest example. It is also hypohamiltonian: removing any one vertex leaves a graph that does have a Hamiltonian cycle. That combination — close to being Hamiltonian, but not — is why “every cubic bridgeless graph is Hamiltonian” fails so sharply.
It is a snark. The edges cannot be coloured with three colours so that no two edges of the same colour share a vertex. Four colours are necessary and sufficient, so the chromatic index is 4. Petersen introduced the graph in 1898 precisely as a counterexample to the hope that every bridgeless cubic graph is 3-edge-colourable (a hope closely tied to Tait’s approach to the four colour theorem). It was the only known snark from 1898 until 1946, and it is still the smallest. A theorem conjectured by Tutte, and announced in 2001 by Robertson, Sanders, Seymour and Thomas, says that every snark has the Petersen graph as a minor.
It is non-planar, even though it has only ten vertices. It has both K5 and K3,3 as minors, so Kuratowski’s and Wagner’s criteria both apply.
It is very symmetric, but not a Cayley graph. The automorphism group is the symmetric group S5, of order 120. The action is easiest to see from the Kneser construction below: S5 permutes the five underlying elements, and therefore permutes the ten 2-subsets. The graph is vertex-transitive and edge-transitive (in fact 3-arc-transitive), yet it is not a Cayley graph. It is the standard example of “as symmetric as a graph can look without coming from a group acting on itself”.
It is the unique (3, 5)-cage, and the unique (3, 5)-Moore graph: the smallest cubic graph of girth 5, and as large as a 3-regular diameter-2 graph can be. Hoffman and Singleton’s classification of Moore graphs of diameter 2 is often a student’s first meeting with that uniqueness.
Taken together, this is why textbooks keep coming back to it. If you are about to conjecture something about cubic graphs, bridgeless graphs, vertex-transitive graphs, or 3-edge-colourings, the usual advice is to try the Petersen graph first.
The Kneser construction
There is a construction that makes the 120 symmetries obvious, and that does not depend on a particular drawing.
Take a 5-element set, say {1, 2, 3, 4, 5}. Give the Petersen graph one vertex for each 2-element subset. Put an edge between two vertices exactly when the corresponding 2-subsets are disjoint. The result is the Kneser graph KG(5, 2), and it is isomorphic to the Petersen graph.
The ten vertices are 12, 13, 14, 15, 23, 24, 25, 34, 35, 45. The fifteen edges are the disjoint pairs, for example 12—34, 12—35, 12—45, and so on. Each vertex is disjoint from exactly three others, which is why the graph is 3-regular. The same graph is also the complement of the line graph of K5, and the odd graph O3.
Geometrically, it is the graph of vertices and edges of the hemi-dodecahedron: a dodecahedron with opposite vertices, edges and faces identified.
Adjacency list and Python
With the labelling in the drawing (outer 0–4, inner 5–9), the adjacency list is:
0: 1, 4, 5 1: 0, 2, 6 2: 1, 3, 7 3: 2, 4, 8 4: 0, 3, 9 5: 0, 7, 8 6: 1, 8, 9 7: 2, 5, 9 8: 3, 5, 6 9: 4, 6, 7
NetworkX ships this graph as nx.petersen_graph(), with the same 0–9 labelling. You can also build it by hand from the pentagon, the spokes and the star, and check that the two graphs are isomorphic:
import networkx as nx
G = nx.petersen_graph()
assert G.order() == 10 and G.size() == 15
for v in range(10):
print(v, ":", sorted(G.neighbors(v)))
# Outer pentagon, spokes, inner pentagram — same graph as the drawing
H = nx.Graph()
H.add_edges_from(
[(i, (i + 1) % 5) for i in range(5)]
+ [(i, i + 5) for i in range(5)]
+ [(5 + i, 5 + (i + 2) % 5) for i in range(5)]
)
assert nx.is_isomorphic(G, H)
A compact Kneser construction, if you want the 2-subset labels instead of 0–9:
from itertools import combinations
import networkx as nx
verts = list(combinations(range(5), 2))
K = nx.Graph()
K.add_nodes_from(verts)
K.add_edges_from(
(a, b) for a, b in combinations(verts, 2) if set(a).isdisjoint(b)
)
assert nx.is_isomorphic(K, nx.petersen_graph())
FAQ
What is the Petersen graph?
It is an undirected 3-regular graph with 10 vertices and 15 edges. It is most often drawn as a pentagon with a pentagram inside it and five spokes joining them. It is a standard example and counterexample in graph theory.
Why is the Petersen graph famous?
It sits at the intersection of several classical questions and is small enough to draw by hand. It is the smallest snark, the smallest hypohamiltonian graph, the unique (3, 5)-cage, and a highly symmetric graph that is nonetheless not a Cayley graph. Many plausible-sounding theorems fail on it and almost nowhere smaller.
How many vertices and edges does the Petersen graph have?
Ten vertices and fifteen edges. Each vertex has degree 3.
Is the Petersen graph planar?
No. It cannot be drawn in the plane without crossings. Its crossing number is 2. It can be embedded without crossings on a torus and on the projective plane.
Does the Petersen graph have a Hamiltonian cycle?
No. It has a Hamiltonian path, but no Hamiltonian cycle. It is hypohamiltonian: deleting any single vertex leaves a Hamiltonian graph.
What is the chromatic number of the Petersen graph?
The chromatic number is 3: the vertices can be coloured with three colours so that no edge joins two vertices of the same colour, and two colours are not enough. The chromatic index (edge-chromatic number) is 4, which is why the graph is a snark.
How do you draw the Petersen graph?
Draw a regular pentagon, a smaller pentagram inside it, and join each outer vertex to the corresponding inner vertex with a spoke. The inner edges skip one inner vertex each time, so they form a five-pointed star rather than a smaller pentagon.
How do you generate the Petersen graph in Python?
networkx.petersen_graph() returns it, with vertices labelled 0–9. You can also build it from an outer pentagon, five spokes and an inner pentagram, or as the Kneser graph KG(5, 2).
Why does the Petersen graph show up in graph theory courses?
Because it is the smallest graph that is simultaneously cubic, non-Hamiltonian, non-planar, 4-edge-chromatic, and highly symmetric. It is the example instructors use once the obvious families (complete graphs, cycles, trees, grids) have been exhausted, and it is the first graph many people are told to test a new conjecture on.
Related: bipartite graphs explained: why the Petersen graph is not bipartite (those 5-cycles), what K3,3 is, and a one-line NetworkX test. Or switch to arrows: directed acyclic graphs explained, the graph behind build systems, git history and backpropagation. The hypercube graph explained is the bipartite regular graph whose edges flip a single bit.
The graph on a shirt
The same 10-vertex drawing is the centre-chest graphic on the Edge Case oversized tee in the Graphs collection: white and red on an oversized faded AS Colour 5082, with the relu logo on the left sleeve. If you want the Petersen graph on a shirt, that is the one. The rest of the line — hypercube, Erdős–Rényi, scale-free, small-world, complete graph — is on the Graphs collection. The Edge Case tee is at reluactivation.com/products/edge-case-oversized-tee. Buying it as a present? See our gifts for mathematicians guide.
Sources
Facts on this page were checked against the following, on 11 November 2026 (Europe/Budapest, UTC+1). Recent or unsettled claims that appeared on Wikipedia in 2026 (in particular, informal reports about the Petersen colouring conjecture) are not used here.
- Wikipedia, Petersen graph. Vertices, edges, radius, diameter, girth, automorphism group S5 of order 120, chromatic number 3, chromatic index 4, fractional chromatic index 3, non-planarity and crossing number 2, hypohamiltonicity, Kneser graph KG(5, 2), snark and snark-minor theorem, strongly regular parameters, spectrum and characteristic polynomial, spanning-tree count, Kempe 1886 and Petersen 1898, Knuth quotation, unit-distance and hemi-dodecahedron remarks.
- Weisstein, Eric W., Petersen Graph, MathWorld. Cubic graph on 10 vertices and 15 edges; unique (3, 5)-cage and unique (3, 5)-Moore graph; girth 5, diameter 2, chromatic number 3, chromatic index 4; non-planar; non-Hamiltonian and smallest hypohamiltonian graph; generalized Petersen graph G(5, 2); Kempe 1886 / Petersen 1898 history.
- Petersen, J. (1898). “Sur le théorème de Tait.” L’Intermédiaire des Mathématiciens, 5, 225–227.
- Kempe, A. B. (1886). “A memoir on the theory of mathematical form.” Philosophical Transactions of the Royal Society of London, 177, 1–70.
- Hoffman, A. J., and Singleton, R. R. (1960). “On Moore graphs of diameter two and three.” IBM Journal of Research and Development, 4(5), 497–504.
- Holton, D. A., and Sheehan, J. (1993). The Petersen Graph. Cambridge University Press.
- Knuth, D. E. The Art of Computer Programming, Volume 4, draft of §7 (the “remarkable configuration” sentence is quoted from this discussion of the graph).
- NetworkX documentation, networkx.petersen_graph.