Prove the Petersen Graph Is Nonplanar Using Euler's Formula

The Petersen graph cannot be drawn in the plane without edge crossings. Euler’s formula gives a short proof once you combine it with a second fact about the graph: its shortest cycle has length 5. That fact forces every face in a hypothetical planar drawing to have a boundary of length at least 5.

The graph’s counts and shortest cycle

The Petersen graph has 10 vertices and 15 edges. One way to describe it is with outer vertices $u_0,\ldots,u_4$ and inner vertices $v_0,\ldots,v_4$, with indices taken modulo 5. Its edges are

• $u_i u_{i+1}$ around the outer pentagon;
• $u_i v_i$ joining corresponding outer and inner vertices;
• $v_i v_{i+2}$ around the inner star.

The graph has girth 5, meaning its shortest cycle has 5 edges. To check that it has no 3- or 4-cycles, notice that a cycle crossing between the outer and inner vertices must use an even number of joining edges. With exactly two joining edges, a cycle of length at most 4 would need one outer edge and one inner edge joining the same two indices. But outer edges connect indices differing by $1$ modulo 5, while inner edges connect indices differing by $2$. That cannot happen. Four joining edges cannot form a cycle because those edges alone are disjoint. A cycle using no joining edges stays on one of the two 5-cycles. The outer pentagon itself is a 5-cycle, so the girth is exactly 5.

The graph also has no bridges: every edge lies on a cycle. The outer and inner edges lie on their respective 5-cycles; for example, each joining edge $u_i v_i$ lies on the cycle $u_i,u_{i+1},v_{i+1},v_{i+3},v_i,u_i$. This detail ensures the face-boundary count below applies even if a face boundary is described as a walk rather than a simple cycle.

Apply Euler’s formula

Suppose, for contradiction, that the Petersen graph has a planar embedding. It is connected, so Euler’s formula gives

$$V-E+F=2.$$

Substitute $V=10$ and $E=15$:

$$10-15+F=2, \qquad F=7.$$

So any planar embedding would have 7 faces.

In a connected plane graph, the sum of the lengths of all face boundaries is $2E$: each edge is counted once for each side. Here that sum would be

$$\sum_{\text{faces } f}\operatorname{length}(f)=2(15)=30.$$

Because the graph has no bridges, no face boundary traverses an edge twice. Each boundary is a closed walk, and any such walk contains a cycle. Since every cycle has at least 5 edges, every face boundary has length at least 5. Therefore 7 faces would require a total boundary length of at least

$$7\cdot 5=35.$$

That contradicts the required total of 30. Hence the Petersen graph is nonplanar.

The equivalent edge-bound argument

The same count can be written as a general planar-graph bound. For a connected planar graph with at least one edge, girth at least 5, and no bridges, every face has length at least 5, so $2E\geq 5F$. Combining this with $F=2-V+E$ gives

$$2E\geq 5(2-V+E) \quad\Longrightarrow\quad E\leq \frac{5}{3}(V-2).$$

For $V=10$, this requires $E\leq \frac{40}{3}$, so the integer edge count must be at most 13. The Petersen graph has 15 edges, again ruling out planarity.

Common mistakes

• Using Euler’s formula by itself: Euler’s formula does not rule out planarity here; it merely predicts 7 faces under the assumption of a planar embedding. The girth condition supplies the contradiction.
• Assuming every planar face has at least 5 edges: That is not true for every planar graph. Triangles and quadrilaterals can bound faces. The lower bound applies here because the Petersen graph has girth 5 and no bridges.
• Counting each edge only once: In the sum of face-boundary lengths, each edge contributes twice, once for each side. That is why the total is $2E=30$, not 15.