A planar graph on $n \geq 3$ vertices has at most $3n-6$ edges: is the converse true?

Question

I know by Euler's formula that if $G=(V,E)$ is planar on $n \geq 3$ vertices, then $|E|\leq 3n-6$. Is the converse true?

If not, how to prove that le cube below is planar ?

Answer 1

No, for example consider the graph $K_{3,3}$ which has $9$ edges and $6$ vertices. It is not planar but $9\le (3\times 6)-6=12$.

Answer 2

As shahab showed, a graph with $m \le 3n-6$ need not be planar (here $m$ is $|E(G)|$ and $n = |V(G)|)$. To answer your question on how to prove that $Q_3$ is planar: simply present a drawing of $Q_3$ in the plane with no edges crossing. this is sufficient to show planarity. If this technique fails (which it won't in this case), one can always show that a $K_{3,3}$ minor or subdivision is impossible for a given graph along with showing that a $K_5$ minor (or subdivision) is impossible. For example: take any tree and add 3 edges to it, say $e_1,e_2,e_3$. The resulting graph is still planar. we can prove this in the following way.

Let $T$ be a tree, and let $X = \{e_1,e_2,e_3\}$ be 3 edges not in $T$. Then $T + X$ is planar. Let $m = |E(T)|$, and let $n = |V(T)|$. Then, $m' = |E(T) + X| = n-1+3 = n+2$. Assume, to the contrary, that $T+X$ is non-planar. Then, by Kuratowski's theorem, $T+X$ contains a subdivision of $K_5$ or a subdivision of $K_{3,3}$. Let $s$ be the number of subdivisions in a graph. Any subdivision of $K_5$ has $5+s$ vertices and $10+s$ edges. If our graph does contain a $K_5$ division, then we can find a set of $5+s$ vertices with $10+s$ edges between them. Likewise, if our graph contained a subdivision of $K_{3,3}$ we could find $6+s$ vertices with $9+s$ between them. However, any set of $5+s$ vertices in $T+X$ gives us a maximum of $5+s-1+3=7+s$ edges between those vertices. Similarly, any set of $6+s$ vertices in $T+X$ gives us a maximum of $6+s-1+3=8+s$ edges. In any case, a contradiction is produced, and so it must be the case that $T+X$ is planar.

You could use this example to show that your graph is planar, but as I've said before: it is much more prudent to simply produce a drawing of your graph in the plane with no edges crossing. The technique above works when you don't know exactly what the graph looks like, or need to prove a general result over a specific class of graphs.