Maximal planar graphs

graph theory

Consider a maximal planar graph of order at least $3$. I'm trying to prove that it cannot have a vertex $v$ of degree $1$. First of all is this correct?
If it is here is an approach I found:

If $v$ has 1 neighbor then you could remove $v$ and still have a maximal planar graph, but with $n−1$ vertices and $3n−5$ edges contradicting that it should have $3(n−1)−6=3n−12$ edges.
Is this correct?

Best Answer

Yes, this is essentially correct. There is one slight niggle: you have assumed the number of edges for a maximal planar graph on $k$ vertices is $3k-6$, but that only holds for $k\geq 3$. Since you apply this with $k=n-1$, your argument assumes $n\geq 4$ and you need to check the (easy) case $n=3$ separately.