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

Question

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?

Answer 1

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.