Prove that Petersen Graph is nonplanar

In this article, we will show that Petersen Graph is non-planar.

Petersen Graph: Petersen Graph is a Cubic Graph with 10 vertices and 15 edges such that each vertex has degree 3. There is no 3-cycle or 4-cycle in the Petersen Graph.

Non-planar Graph: A graph is called a non-planar graph if it is impossible to draw the graph on a 2-D plane such that no two edges intersect.

petersen graph

Proof

We will proof Petersen Graph is non-planar using Kuratowski’s theorem.

According to Kuratowski’s theorem, a graph is non-planar if and only if one of its sub-graph is homeomorphic to K3,3 or K5.

A Graph G1 is homeomorphic to Graph G2 if we can convert G1 to G2 by sub-division or smoothing.

Sub-division: Suppose an edge (v,u). Sub-division means removing edge (v,u) and adding a vertex w and two new edges (v,w) and (w,u).

subdivision

Smoothing: Suppose edges (v,w) and (w,u) such that degree of w is 2. Smoothing means removing vertex w and adding a new edge (v,u).

smoothing

We will show that a sub-graph of Petersen Graph is homeomorphic to K3,3.

First remove vertex 0 from Petersen Graph.

prove petersen graph is homeomorphic to K3,3

After that, perform smoothing on vertex 2, vertex 3, and vertex 6. In simple words, remove vertex 2 and add a new edge (4,8). Remove vertex 3 and add a new edge (1,9). Then remove vertex 6 and add a new edge (5,7).

removing vertices from graph

Rearrange the vertices of the above graph. Put all the vertices which are not adjacent in one set.
Place vertex 9, 4, 7 on the left side and 5, 8, 1 on the right side.

Complete bipartite Graph K3,3

It is clear that the graph obtained is K3,3. Thus, a sub-graph of Petersen Graph is homeomorphic to K3,3. Therefore, by Kuratowski’s theorem, Petersen Graph is non-planar.

References

Kuratowski’s theorem

Leave a Comment

Your email address will not be published. Required fields are marked *