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 **K _{3,3 }or K_{5}**.

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 **K _{3,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 **K _{3,3}**. Thus, a sub-graph of Petersen Graph is homeomorphic to K

_{3,3}. Therefore, by Kuratowski’s theorem,

**Petersen Graph is non-planar**.

**References**