Kuratowski's Theorem and Planar Graphs

Question

Suppose there is a non-planar graph $G$ with $E$ edges and $V$ vertices, and that $G-e$ is planar for every edge $e$ of the graph. I am asked to show that $E-V=3$ or $E-V=5$. I know that I am supposed to use the fact that if $G$ contains $K_5$ or $K_{3,3}$, it is not planar. But I am not really now sure how to start proving this. Any ideas?

Answer 1

Assume that $G=(V,E)$ is non-planar, and that for every $e\in E$ $G-e$ is planar.

I use the definition used on the wikipedia page of Kuratowski theorem.

Let show that $G$ is a subdivision of $K_5$ or $K_{3,3}$. (Note that in fact there can be some additional disconnected vertices, but I'll assume here for clarity that the graph is connected).

Assume toward contradiction $G$ is not a subdivision of $K_5$ or $K_{3,3}$. By Kuratowski theorem we know that there exists $H=(V',E')$ a Kuratowski subgraph of $G$. By hypothesis we know that $E\setminus E'\neq \emptyset$ (otherwise $G=H$), we also know that for all $e\in E\setminus E'$, $G-e$ is planar, but $H$ is also a subgraph of $G-e$. Contradiction.

Thus $G$ is a subdivision of $K_5$ or $K_{3,3}$.

Notice that for $K_5$ $E-V=5$ and for $K_{3,3}$ $E-V=3$. Notice also that the subdivision preserve this quantities since the subdivision of an edge add exactly one edge and one vertex. Thus for $G$, $E-V=5$ or $E-V=3$, as it is a subdivision of $K_5$ or $K_{3,3}$.

Answer 2

Part 1 Using Kuratowski theorem : Suppose we have non-planar graph $G$, so there is subgraph $G' \in G$ , which homomorphing to $K_{5}$ or $K_{3 3}$. Also we know that for every $e$ from edge-set $G\e$ is planar. Assume that we delete this edge from $G\G'$ , so in new graph we have a subgraph $G'$. Because of this we should delete edge from $G'$, but we know that we could select any edge from $G$, so our $G$ full homomorphing to $K_{5}$ or $K_{3 3}$. Part 2 (I'm not sure about it) So we know that our $G$ is homomorphing to our non-planar graphs. Now the main question is : are there graphs satisfying the condition of the edges and different from $K_{5}$ or $K_{3 3}$. Ok, we have invariant for them: $E-V=5$ or $E-V=3$. Why is it invariant? Ok, consider homomorphism: we could split one edge on two and add one vertex or merge two edge and delete one vertex. So we have our famous non-planar graph lets build another graph using only homomorphism. We know that our conditions about edges are meet our graphs ($K_{5}$ or $K_{3 3}$), so consider our building : we always add one edge and one vertex , or delete them, so we save our invariant.

Now we know that $G$ save the invariant.