4
$\begingroup$

Consider the following graph $G $: $V (G) =\{1,2,3,4,5\}$ and $E (G)=\{12,13,23,24,34,15,45,25,35\} $. The question is whether it is planar or not.

I think it is not planar because I am not able to draw it without edge intersections. However if it is not planar it should contain a subdivision of $K_5$ or $K_{3,3}$. It cannot contain a subdivision of $K_{3,3}$ since any such subdivision has at least $6$ vertices. It cannot contain a subdivision of $K_{5}$ since any such subdivision has at least $10$ edges. Where am I going wrong?

$\endgroup$
  • 1
    $\begingroup$ It is planar; it can be drawn on the plane without self-intersections. Have another go! $\endgroup$ – Lord Shark the Unknown Aug 25 '18 at 17:17
5
$\begingroup$

enter image description here

Furthermore, your proof is valid.

$\endgroup$

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.