# Is Petersen Graph without an edge planar

Let G be the Petersen graph. Is G-e planar? If no, explain why. If G-e is planar, then draw a plane graph isomorphic to it. So we can remove 3 types of edges. 1) Connecting 2 vertices on the outside (eg. 0-1). 2) Connecting an inside and an outside vertice (eg. 4-9). 3) Connecting 2 inside vertices (eg. 5-7). It's also clear that we need the edges of type 3 to not cross over each other.

Removing 1) adds no benefit. Because even if we remove the edge, we'd have to cross another outer edge to connect 2 inner vertices. For eg. removing 0-1 so we can connect 6-9. This would not yield results since we'd still have to cross either 0-4 or 0-5 (or any corresponding pair).

Removing 2) is also useless. We'd still have other internal edges (type 2) to cross. For example if we remove 0-5, we can loop 6-9 around 5 to connect them. But we can't do the same for 6-8 which is seperated by 2 regions.

Quick inspection shows same result for 3) This is my working theory. That G-e is nonplanar because removing any one edge still leaves other vertices seperated by 2 regions. Is there a better way to articulate this. Am I just wrong?

• Your conclusion is correct, but I'm not sure your argument is. I find it hard to follow. I think you can make a more convincing argument along the lines in this answer. The Petersen graph doesn't have a Hamilton cycle, but the cycle $0123496750$ will work. Nov 6, 2020 at 13:48

It is still not planar.

First, we delete three edges as follows, and label the vertices. Then, we reduce the vertices of the same color: 1,6; 5,7; 3,4 and obtain a $$K_{3,3}$$ Removing only one edge still doesn't make it planar. This is because after removing one edge, we have $$v=10$$, $$e=14$$, and girth $$g=5$$. Now, $$f=2-v+e=2-10+14=6$$ and $$2e\ge gf\implies 2\times 14\ge 5\times 6\implies 28\ge 30$$ which is a contradiction.

Note that the inequality in the last line is the same one that proves that the Petersen graph is non-planar. It follows from the fact that each face is surrounded by a minimum of $$g$$ edges and each edge can border $$2$$ faces of a graph.

Just as a sidenote, removing $$2$$ edges however makes the graph planar (and hence you need to remove atleast two edges to make it planar) as shown below- 