How to prove that every maximal outerplanar graph has exactly 2n-3 edges without induction?

975 Views Asked by At

I recently saw such an interesting theorem.

Every maximal outerplanar graph has exactly 2n-3 edges.

A similar question is here Every maximal outerplanar graph has exactly 2n-3 edges.

I have seen that many textbooks basically use induction, provided that there must be a 2-degree vertex. This is very good, but I feel that there should be a more natural proof method.

I did some attempts but failed. Let $n$, $m$ and $f$ be number of vertices,edges and faces respectively. First of all, we know that each inner face is 3-circle, and the length of the exterior face is $n$. Let $f_3$ be number of $3$-face. $$3f_3+n=2m$$ Then combine Euler's formula: $$n-m+f=2$$ and $$f_3+1=f.$$

But there is no expectation to get the value of $f_3$ or $m$.

1

There are 1 best solutions below

1
On BEST ANSWER

$3f-3+n=2m$, $n-m+f=2$, $3n-3m+3f=6$, $3+2n-3m=6-2m$, $2n=3+m$, done.