1
$\begingroup$

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:

enter image description here

  • 0
    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?2012-11-22

2 Answers 2

12

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. GraphG Here is a step-by-step solution for graph H. GraphH

  • 1
    Did you really want to do OP's homework? Not leave anything for OP to work out on his/her own?2012-11-23
5

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".