$\begingroup$
How do I prove this graph is nonplanar? It has 11 vertices and 25 edges, with a girth of 3.
$\endgroup$ 101 Answer
$\begingroup$Delete the center vertex and you're left with a graph $G$ that has $10$ vertices and $20$ edges. By Euler's formula, if $G$ were planar, it would need to have $12$ faces in any plane embedding.
Since $G$ has no triangles (all triangles of the original graph passed through the center vertex, which you can check), each face would have at least $4$ sides. This gives at least $48$ edges, counted twice; therefore $G$ would need to have at least $24$ edges. But $G$ has only $20$ edges, contradiction.
$\endgroup$ 2
