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

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)$.

enter image description here

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?

  • $\begingroup$ It's not called subgraph, it's called a minor. $\endgroup$ – Arthur Apr 27 '16 at 6:37
  • $\begingroup$ 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. $\endgroup$ – wythagoras Apr 27 '16 at 6:39
  • 1
    $\begingroup$ 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}$. $\endgroup$ – 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.

  • $\begingroup$ Can you please explain how you came to that answer? I want to see the logic involved in those steps from the original. $\endgroup$ – Jodo1992 Apr 27 '16 at 6:42
  • $\begingroup$ So for each individual graph, it's a bit of a guessing game then? $\endgroup$ – Jodo1992 Apr 27 '16 at 7:01
  • 2
    $\begingroup$ @Jodo1992 Yes, it usually is. $\endgroup$ – wythagoras Apr 27 '16 at 7:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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