Constructing the Petersen Graph

Building the Graph from Two Layers

The Petersen graph is a standard finite simple graph, but its familiar drawings can make the construction harder to read than the definition. We will specify it entirely by its vertices and edges. The construction uses an outer cycle of five vertices, an inner set of five vertices joined in a different cyclic order, and five edges connecting corresponding outer and inner vertices. No picture is needed to determine whether an edge is present.

Throughout, indices belong to \(\{0,1,2,3,4\}\) and are read modulo \(5\). Thus, for example, an index of \(5\) means \(0\), and an index of \(-1\) means \(4\). The symbols \(u_i\) and \(v_i\) name different vertices for every pair of indices: no \(u_i\) is equal to any \(v_j\).

The outer vertices follow the order \(u_0,u_1,u_2,u_3,u_4,u_0\). The inner vertices follow the order \(v_0,v_2,v_4,v_1,v_3,v_0\), so each inner edge joins indices differing by \(2\) modulo \(5\). The spokes join \(u_i\) to \(v_i\). This difference between the outer and inner index orders is essential: joining \(v_i\) to \(v_{i+1}\) would define a different graph.

When edges are listed using indices, an edge such as \(v_3v_0\) is the same undirected edge as \(v_0v_3\). We count it only once. The three edge types are also visibly separated by their endpoints: an outer edge has two \(u\)-vertices, an inner edge has two \(v\)-vertices, and a spoke has one of each.

Why the Construction Has Ten Vertices and Fifteen Edges

Proof. There are five distinct symbols \(u_0,\ldots,u_4\) and five distinct symbols \(v_0,\ldots,v_4\); the two sets of symbols are disjoint. Therefore the vertex set contains \(5+5=10\) distinct vertices. For the outer list, each edge has different endpoints, and the five consecutive pairs around a cycle of length \(5\) are distinct. The same is true of the inner list: each pair has different endpoints, and the five successive pairs in the order \(v_0,v_2,v_4,v_1,v_3,v_0\) are distinct. Each spoke also has different endpoints, since its endpoints have different letter names, and the five spokes have different index pairs. No outer edge can equal an inner edge or a spoke, because the three types have different combinations of \(u\)- and \(v\)-endpoints. Thus there are no loops or repeated edges, so the graph is simple. The three disjoint edge lists each contain five edges, giving \(|E(P)|=5+5+5=15\). \(\square\)

This count uses the fact that edges are undirected and that the listed types do not overlap. It does not count a spoke once from each endpoint: \(u_iv_i\) is a single edge, not two directed edges. The order and size are properties of this specified graph, not consequences of how a drawing happens to look.

Checking the Degrees Directly

Proof. Fix an index \(i\) modulo \(5\). From the outer edge rule, \(u_i\) is adjacent to \(u_{i-1}\) and \(u_{i+1}\). It is also adjacent to \(v_i\) by the spoke rule. These are three distinct vertices: the two \(u\)-vertices have different indices because \(i-1\) and \(i+1\) differ by \(2\), which is not \(0\) modulo \(5\), and \(v_i\) is not a \(u\)-vertex. The edge lists contain no other edges incident with \(u_i\), so \(\deg(u_i)=3\). For \(v_i\), the inner rule gives neighbors \(v_{i-2}\) and \(v_{i+2}\), and the spoke gives neighbor \(u_i\). The two inner neighbors are distinct because their indices differ by \(4\), which is not \(0\) modulo \(5\); neither is \(u_i\). There are no other edges incident with \(v_i\). Hence \(\deg(v_i)=3\). Since \(i\) was arbitrary, every vertex has degree \(3\). \(\square\)

This direct check also gives an independent verification of the edge count. The sum of the ten vertex degrees is \(10\cdot3=30\). Every undirected edge contributes \(1\) to the degree of each of its two endpoints, so the degree sum is twice the number of edges. Consequently the number of edges is \(30/2=15\), agreeing with the count from the three edge lists.

Using Different Labels

A graph can be described with different vertex names without changing which vertices are adjacent. An explicit relabeling is useful when comparing the layered definition with an edge list that uses consecutive integers. We give one such list and verify it by applying the same naming rule to all three edge types.

In that edge list, spaces in expressions such as \(8\,10\) separate the two endpoint labels; they do not indicate multiplication. Writing a comma-separated edge set makes the endpoints unambiguous. The relabeling is not a new construction: it is the same graph with new names, and each old edge has exactly one corresponding new edge.

Common Construction and Counting Mistakes

Using the wrong inner step. If the inner rule is changed to \(v_iv_{i+1}\), the inner edges become \(v_0v_1,v_1v_2,v_2v_3,v_3v_4,v_4v_0\), rather than the required list \(v_0v_2,v_1v_3,v_2v_4,v_3v_0,v_4v_1\). Both lists have five edges, so counting alone will not detect the mistake. The correction is to follow the defining step of \(2\) modulo \(5\), not \(1\).

Counting each spoke twice. A common incorrect total is \(5+5+10=20\), on the mistaken assumption that each of the five spokes must be counted once from its \(u\)-endpoint and again from its \(v\)-endpoint. Edges are undirected: the spoke \(u_iv_i\) is one edge with two endpoints. The correct total is \(5+5+5=15\). As a separate check, the ten vertices each have degree \(3\), so the degree sum is \(30\), and dividing by \(2\) gives \(15\) edges.

The edge-list construction is useful because it fixes the graph independently of a drawing, while the degree check provides a second way to verify the count. Together, these checks make it possible to recognize the intended graph even when it is presented with a different layout or different vertex labels.