4
$\begingroup$

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.

enter image description here

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?

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – saulspatz
    Commented Nov 6, 2020 at 13:48

2 Answers 2

2
$\begingroup$

It is still not planar.

First, we delete three edges as follows, and label the vertices.

enter image description here

Then, we reduce the vertices of the same color: 1,6; 5,7; 3,4 and obtain a $K_{3,3}$

enter image description here

$\endgroup$
2
$\begingroup$

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- enter image description here

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .