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?