3
$\begingroup$

Graph planar or not

So the question is whether the graph given is planar or not. After some trial and error I think it is NOT planar, so I want to prove it using Kuratowski's Theorem but I couldn't break it down to $K_5$ or $K_{3,3}$. Would appreciate any help on this!

Also in general, is there any strategy that we can use when trying to apply Kuratowski's Theorem? Or any thing that can help to determine whether we should aim for $K_5$ or $K_{3,3}$? Or is it just purely trial and error? I got so frustrated when I could not figure it out.

$\endgroup$
  • $\begingroup$ What version of Kuratowski do you use: the one with minors? or subgraphs by subdivisions? $\endgroup$ – Henno Brandsma Oct 27 '18 at 5:28
  • 3
    $\begingroup$ There aren't too many points of degree 4, so I'd say go for $K_{3,3}$, $\endgroup$ – Henno Brandsma Oct 27 '18 at 5:29
8
$\begingroup$

Remove the edge $BD$ and suppress vertices $B,D$. The original graph thus contains a subdivision of this resulting graph, which is isomorphic to $K_{3,3}$, so the original graph is not planar.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for your answer! $\endgroup$ – M. W Oct 27 '18 at 8:46

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.