The Petersen Graph As A Counting Example

Two Descriptions of One Graph

The Petersen graph is a useful small example because two simple descriptions make different features visible. One description uses an outer pentagon, an inner five-pointed star and five spokes. The other treats each vertex as a 2-element subset of a 5-element set, with two vertices adjacent exactly when their subsets are disjoint. The second description makes it possible to check degrees and short cycles by counting subsets.

Throughout, graphs are finite and simple. A cycle of length \(k\) is a closed sequence of \(k\) edges whose vertices before the return to the starting vertex are distinct, with \(k\ge 3\). The requirement \(k\ge 3\) is part of the definition: traversing an edge and immediately returning along it is a closed walk of length two, not a cycle.

There are \(\binom{5}{2}=5\cdot4/2=10\) vertices. For a vertex representing a subset \(A\), an adjacent vertex must be a 2-subset of the three elements in \(S\setminus A\). There are \(\binom{3}{2}=3\) such subsets. Thus every vertex has degree three. The degree sum is \(10\cdot3=30\), and each edge contributes two to that sum, so the graph has \(30/2=15\) edges.

The Pentagon, Star and Spokes

Here is an explicit labeling that gives the familiar drawing without relying on a picture. Indices in this paragraph are taken modulo \(5\). Let the outer vertices be \(a_i=\{i,i+2\}\), and let the inner vertices be \(b_i\), as listed below. In the disjointness model, use the following vertex correspondence:

In this labeling, the vertex set is \(V=\{a_0,a_1,a_2,a_3,a_4,b_0,b_1,b_2,b_3,b_4\}\). Its edge set is

The first five edges form the outer pentagon in the order \(a_0,a_1,a_2,a_3,a_4,a_0\). The second five form the inner star: following \(b_0,b_2,b_4,b_1,b_3,b_0\) traces its 5-cycle. The last five are the spokes. In the subset model, \(a_i\) and \(a_{i+1}\) are disjoint, \(b_i\) and \(b_{i+2}\) are disjoint, and \(a_i\) and \(b_i\) are disjoint for every listed index. These are precisely the fifteen disjoint pairs.

Why There Are No 3-Cycles or 4-Cycles

Proof. A 3-cycle in the disjointness model would require three pairwise disjoint 2-subsets of \(S\). Pairwise disjoint 2-subsets contain six distinct elements altogether, but \(S\) has only five elements. Therefore no 3-cycle exists.

Suppose there were a 4-cycle \(A,B,C,D,A\), where each capital letter denotes a distinct 2-subset. The 2-subsets \(B\) and \(D\) are distinct, so their union contains at least three elements. Both \(A\) and \(C\) must be disjoint from \(B\cup D\). If that union contains four or five elements, fewer than two elements remain outside it, and no 2-subset can be disjoint from both \(B\) and \(D\). If it contains three elements, exactly two elements remain, so there is only one 2-subset disjoint from both: the 2-subset consisting of those two remaining elements. In that case \(A=C\), contradicting that the four vertices of the cycle are distinct. Every possibility leads to a contradiction, so there is no 4-cycle. \(\square\)

The girth of a graph is the length of its shortest cycle. The Petersen graph does have a 5-cycle, namely its outer pentagon, and the theorem excludes cycles of lengths three and four. Thus its girth is five. This conclusion depends on the convention \(k\ge3\) in the definition of a cycle; an edge traversed forward and backward does not count as a 2-cycle.

Counting the 5-Cycles

Proof. We count the 5-cycles through one fixed vertex, then count incidences between vertices and 5-cycles. Fix \(A=\{1,2\}\). Its neighbors are \(B_1=\{3,4\}\), \(B_2=\{3,5\}\), and \(B_3=\{4,5\}\). A 5-cycle through \(A\) uses two distinct neighbors of \(A\). There are \(\binom{3}{2}=3\) choices for this unordered pair.

The permutations of \(\{3,4,5\}\), while fixing 1 and 2, preserve disjointness and act transitively on the three unordered pairs of neighbors. It is therefore enough to count the cycles for the pair \(B=\{3,4\}\), \(E=\{3,5\}\). Fix the direction \(A,B,C,D,E,A\); reversing a cycle gives its unique direction that starts from \(A\) through \(B\).

For \(C\) to be adjacent to \(B\), it must be a 2-subset of \(\{1,2,5\}\). It cannot equal \(A=\{1,2\}\), so \(C\) is either \(\{1,5\}\) or \(\{2,5\}\). For \(D\) to be adjacent to \(E\), it must be a 2-subset of \(\{1,2,4\}\); excluding \(A\), it is either \(\{1,4\}\) or \(\{2,4\}\). If \(C=\{1,5\}\), the only listed choice for \(D\) disjoint from \(C\) is \(\{2,4\}\). If \(C=\{2,5\}\), the only listed choice disjoint from \(C\) is \(\{1,4\}\). Thus there are exactly two cycles for this neighbor pair. Each of the three pairs gives two cycles, so \(A\) lies on \(3\cdot2=6\) 5-cycles.

The same count holds at every vertex: a permutation of the five elements sends any 2-subset to any other and preserves disjointness. There are ten vertices, each on six 5-cycles, giving \(10\cdot6=60\) vertex-cycle incidences. Each 5-cycle contains five vertices, so the number of distinct 5-cycles is \(60/5=12\). \(\square\)

What the Counting Reveals

The two models complement each other. The pentagon-and-spokes description displays five particular 5-cycles immediately: the outer pentagon and the inner star cycle. The disjointness model makes the degree calculation and the exclusions of 3- and 4-cycles short. The count above goes further: it shows that these visible cycles are part of a total of twelve 5-cycles.

Care is needed when making claims about cycle lengths. Proving there are no triangles or 4-cycles establishes girth five once a 5-cycle is exhibited; it does not by itself enumerate cycles of every larger length. The counting argument here is specifically for cycles of length five.

Common Pitfalls

Counting a closed edge traversal as a cycle. If \(uv\) is an edge, the sequence \(u,v,u\) has length two and is closed. It is not a cycle: a cycle must have length at least three and distinct vertices before returning to its start. In particular, this traversal does not make the Petersen graph's girth two.

Forgetting the factor of two in the degree sum. The ten vertices each have degree three, giving a degree sum of \(10\cdot3=30\), not thirty edges. Every edge has two endpoints, so the edge count is \(30/2=15\).

Counting a cycle more than once. A cycle can be written starting at any of its vertices and in either direction. In the 5-cycle count, we fix \(A\) and an unordered pair of its neighbors, then choose the direction that starts through \(B\). For the final total, each cycle is counted once at each of its five vertices, which is why the incidence count is divided by five.