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
  • 1
    $\begingroup$ It is planar; it can be drawn on the plane without self-intersections. Have another go! $\endgroup$
    – Angina Seng
    Aug 25, 2018 at 17:17

1 Answer 1

Reset to default
5
$\begingroup$

enter image description here

Furthermore, your proof is valid.

$\endgroup$

You must log in to answer this question.