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
    Nov 6, 2020 at 13:48

2 Answers 2

1
$\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$
1
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.