# Prove that a graph is a planar embedding using Kuratowski's Theorem or prove that none exists.

Having trouble with my homework. It goes like this:

For each of G and H below, either give a planar embedding of the graph, or use Kuratowski’s Theorem to prove that none exist.

I know Kuratowski's Theorem states that if we can find a subgraph $K_{3,3}$ or $K_5$. The graphs look like this:

-
Kuratowski says a subgraph homeomorphic to $K_{3,3}$ or $K_5$. The graph on the left has no vertex of degree $4$, so you won't find a $K_5$ there. Better look for a $K_{3,3}$ (or else try to find a planar embedding). –  Gerry Myerson Nov 22 '12 at 22:40
What are the rules of finding a $K_{3,3}$ graph? Can we use edge deletions and edge contractions. Could you give me some tips? –  Help Nov 22 '12 at 22:56

None of them is planar.

Green means the vertex and nearby edges will be merged into one edge in the next step.

Red means the edge will be deleted in the next step.

Orange means the vertex will be moved in the next step.

Here is a step-by-step solution for graph G. Here is a step-by-step solution for graph H.

-
Did you really want to do OP's homework? Not leave anything for OP to work out on his/her own? –  Gerry Myerson Nov 23 '12 at 6:03

I won't do the given problem, but I'll do one that may make it clearer how one can proceed. Consider the graph given by the vertices and edges of a cube, together with one body diagonal (that is, one extra edge, passing through the center of the cube, and joining two opposite vertices of the cube). Let's prove this isn't planar by finding a subgraph isomorphic to $K_{3,3}$.

First of all, without that body diagonal, the graph is planar, so our subgraph must include that edge. Let's call its endpoints $A$ and $X$. There are three other vertices adjacent to $A$; pick two of them (by symmetry, it doesn't matter which two) and call them $Y$ and $Z$. So at this point, we have $A$ adjacent to $X$, $Y$, and $Z$.

Now there is another vertex adjacent to all three of $X$, $Y$, and $Z$; call it $B$.

Now there's a vertex, as yet unused, adjacent to both $X$ and $Z$; call it $C$. $C$ is not adjacent to $Y$, but there is a path running from $C$ to $Y$ via vertices we haven't used for anything else. So that gives you a subgraph in which there are independent paths joining each of $A,B,C$ to each of $X,Y,Z$; in other words, a subgraph homeomorphic to $K_{3,3}$; in other words, a proof of nonplanarity of "cube plus body diagonal".

-