Structural Properties of the Petersen Graph

An Explicit Model of the Petersen Graph

The Petersen graph is a small graph with a striking combination of properties: every vertex has the same degree, there are no triangles, and yet the graph contains an odd cycle. An explicit vertex and edge list makes these claims verifiable without relying on a drawing. It also helps prevent a common error: the inner edges do not join consecutive subscripts.

We use subscripts modulo \(5\), so, for example, \(a_5=a_0\). The vertices are divided into an outer set and an inner set. The outer edges join consecutive \(a\)-vertices; each \(a_i\) is joined to \(b_i\); and the inner edges join \(b_i\) to \(b_{i+2}\). All edges are undirected, and the graph is simple: it has no loops or multiple edges.

There are three groups of edges: five outer edges, five edges joining the two sets, and five inner edges. In particular, the inner edges form the cycle \(b_0,b_2,b_4,b_1,b_3,b_0\), not the cycle in subscript order. This organization will let us check degrees and cycles by reading the edge list.

Degree and Triangle Structure

Proof. The neighbors of an outer vertex \(a_i\) are \(a_{i-1}\), \(a_{i+1}\), and \(b_i\), by the three specified types of edges. These are three distinct vertices, so \(\deg(a_i)=3\). The neighbors of an inner vertex \(b_i\) are \(b_{i-2}\), \(b_{i+2}\), and \(a_i\). The two inner neighbors are distinct modulo \(5\), and neither is \(a_i\), so \(\deg(b_i)=3\). Thus every vertex has degree \(3\).

For the triangle claim, divide the vertices into the outer set \(\{a_0,\ldots,a_4\}\) and the inner set \(\{b_0,\ldots,b_4\}\). Among the outer vertices, the only edges form the 5-cycle \(a_0,a_1,a_2,a_3,a_4,a_0\), which has no triangle: each outer vertex has only two outer neighbors, and those two are not adjacent. Among the inner vertices, the only edges form the 5-cycle \(b_0,b_2,b_4,b_1,b_3,b_0\), which likewise has no triangle.

It remains to exclude a triangle using both sets. Such a triangle would have either two outer vertices and one inner vertex, or one outer vertex and two inner vertices. Each \(b_i\) is adjacent to exactly one outer vertex, namely \(a_i\), so it cannot be joined to two outer vertices as required in the first case. Each \(a_i\) is adjacent to exactly one inner vertex, namely \(b_i\), so it cannot be joined to two inner vertices as required in the second case. All possible distributions of three vertices have been covered, so no triangle exists. \(\square\)

Two 5-Cycles and Non-Bipartiteness

A cycle is a closed sequence of adjacent vertices in which no vertex is repeated apart from the final return to the starting vertex. The edge list displays a 5-cycle using only outer vertices and another using only inner vertices. The odd length of either cycle also gives an immediate obstruction to bipartiteness.

Proof. The outer sequence uses edges \(a_0a_1,a_1a_2,a_2a_3,a_3a_4,a_4a_0\), all in \(E(P)\), and its five vertices before returning to \(a_0\) are distinct. It is a 5-cycle. The inner sequence uses \(b_0b_2,b_2b_4,b_4b_1,b_1b_3,b_3b_0\), also all in \(E(P)\); its five vertices before returning to \(b_0\) are distinct as well. It too is a 5-cycle.

A graph is bipartite if its vertices can be partitioned into two sets so that every edge has one endpoint in each set. Along any cycle in a bipartite graph, the vertices must alternate between the two sets. After an odd number of edges the alternating sequence is in the opposite set from where it began. But a cycle returns to its starting vertex, which belongs to the same set as at the start. This is impossible for a cycle of length \(5\). Since \(P\) contains such a cycle, \(P\) is not bipartite. \(\square\)

Reading the Structure Correctly

These properties describe different aspects of the same representation. The degree calculation uses the local list of edges at each vertex. The triangle proof uses the separation into outer and inner vertices, together with the fact that each vertex has just one neighbor across that separation. The cycle and bipartiteness checks use a sequence of five explicitly listed edges. Keeping these arguments distinct makes each claim easy to verify.

A frequent mistake is to read “join \(b_i\) to \(b_{i+2}\)” as “join \(b_i\) to \(b_{i+1}\).” For example, an incorrect calculation might list \(b_0b_1\) as an inner edge because the subscripts are consecutive. That edge is not in \(E(P)\). The actual inner neighbors of \(b_0\) are \(b_2\) and \(b_3\), since the inner edges incident with \(b_0\) are \(b_0b_2\) and \(b_3b_0\). The correction matters: the inner 5-cycle is traversed in the order \(b_0,b_2,b_4,b_1,b_3,b_0\).

Also distinguish between showing that a graph contains a 5-cycle and showing that it is exactly a 5-cycle. The Petersen graph has ten vertices and fifteen edges, while either displayed cycle uses only five vertices and five edges. These cycles are subgraphs of \(P\), not descriptions of the entire graph. Their odd length is enough to prove non-bipartiteness; no claim that the rest of the graph is absent is needed.