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?
Best Answer
Furthermore, your proof is valid.