# How do I create a minor of a $K_5$ or $K_{3,3}$ configuration from this $10$ vertex graph?

I have a graph with $10$ vertices, all of which are degree $3$:

I am trying to show it is either planar or nonplanar, so I use the circle-chord method to create a circuit $abcdefghija$ (easy since the circuit already exists) and then add the chords $(a,f)$, $(b,j)$, $(c,h)$, $(d,i)$, and $(e,g)$.

I put $(b,j)$, $(e,g)$, and $(d,i)$ inside first, then put $(a,f)$ outside using inside-outside symmetry to avoid edge crossing, however, $(c,h)$ now can't be drawn either inside or outside without crossing edges, making the graph nonplanar.

Now I must show that either a $K_5$ or $K_{3,3}$ configuration exists for the nonplanar graph, but I don't know how to whittle $10$ vertices down to either $5$ or $3,3$. How do I do this from a graph with so many vertices?

• It's not called subgraph, it's called a minor. – Arthur Apr 27 '16 at 6:37
• There is actually a difference between a subgraph and a minor. In a subgraph, you can just delete edges and vertices. In a minor, you can also contract edges. – wythagoras Apr 27 '16 at 6:39
• Your latter figure is IMHO a very good start. (+1) Remove the edges $(b,j)$ and $(e,g)$. This makes the vertices $b,j,e,g$ kinda superfluous. So essentially you are left with a graph that has all of $a,d,h$ connected to all of $c,i,f$. That's a $K_{3,3}$. – Jyrki Lahtonen Apr 27 '16 at 7:09

You can create $K_{3,3}$ as following:
• Delete edges $(b,j)$ and $(e,g)$
• Contract edges $(a,b)$, $(a,j)$, $(e,f)$ and $(f,g)$.
First note that for $K_5$ we need 5 edges with degree 4. That could be possible with edge contraction, but it is very unlikely. So we need to find $K_{3,3}$. To find $K_{3,3}$, we need a graph with six vertices with degree three each. I then just tried to contract four edges so that there were only six vertices left. I was lucky that it became $K_{3,3}$. Otherwise, I had tried to contract four other edges.