Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

2 Answers 2

up vote 8 down vote accepted

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

share|improve this answer
1  
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".

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.