# Kuratowski's Theorem and Planar Graphs

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?

• I think you have to show that if $G$ is nonplanar but for every $e$, $G-e$ is planar, then $G$ is very close to being $K_5$ or $K_{3,3}$, like maybe a subdivision of one of those. – Gerry Myerson Feb 14 '16 at 6:33
• I do know that $K_5$ has $E-V=3$ and $K_{3,3}$ has $E-V=5$, but I am not sure how to apply these in the proof. – Arthur L Feb 14 '16 at 7:30
• did you mean subdivision as in an isomorphic form? – Arthur L Feb 14 '16 at 7:33
• "subdivision" means you subdivide one edge into two by putting a vertex of degree on it. – Gerry Myerson Feb 14 '16 at 8:50
• I am interested in this as well, could you give an example of a subdivision in this case? – hysoftwareeng Feb 14 '16 at 20:31

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}$.

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.

• Sorry for my English skills – openspace Feb 17 '16 at 10:09
• Hi, I posted an answer, I think it is really similar to what you posted. If you feel that it is the same, you can copy/past my answer in yours (and tell me) I'll delete my. I tell you this because I believe that your answer is somehow correct (I didn't understand everything because of the english) and I don't want you to have the feeling that I robbed you from your ideas ... – wece Feb 17 '16 at 15:13
• @wece all right, we could keep two versions – openspace Feb 17 '16 at 18:14