Maximal planar graphs

209 Views Asked by At

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?

2

There are 2 best solutions below

1
On 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.

0
On

Assume $v$ has only one neighbour $w$. In a plane embedding of our maximal planar graph $vw$ is an edge of some face. If this face has any vertex $u$ on its boundary apart from $v$ and $w$, we can add $vu$ without breaking planarity, contradicting maximality. Thus the boundary of our fac consists only of vertices $v,x$ and their edge $vw$. Conclude