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.
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).
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).
We will show that a sub-graph of Petersen Graph is homeomorphic to K3,3.
First remove vertex 0 from Petersen Graph.
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).
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.
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