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?

  • $\begingroup$ 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. $\endgroup$ – Gerry Myerson Feb 14 '16 at 6:33
  • 1
    $\begingroup$ 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. $\endgroup$ – Arthur L Feb 14 '16 at 7:30
  • $\begingroup$ did you mean subdivision as in an isomorphic form? $\endgroup$ – Arthur L Feb 14 '16 at 7:33
  • $\begingroup$ "subdivision" means you subdivide one edge into two by putting a vertex of degree on it. $\endgroup$ – Gerry Myerson Feb 14 '16 at 8:50
  • $\begingroup$ I am interested in this as well, could you give an example of a subdivision in this case? $\endgroup$ – 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.

  • $\begingroup$ Sorry for my English skills $\endgroup$ – openspace Feb 17 '16 at 10:09
  • $\begingroup$ 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 ... $\endgroup$ – wece Feb 17 '16 at 15:13
  • $\begingroup$ @wece all right, we could keep two versions $\endgroup$ – openspace Feb 17 '16 at 18:14

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.