# Showing an outerplaner graph has less than $2n-3$ edges

An outerplanar graph is a connected plane graph that can be drawn in such a way that all it's vertices are on the outer face.
I want to show that for every $G$ outerplaner graph with $n$ vertices and $m$ edges, $m\leq 2n-3$
I tried induction and I have a graph on $n$ vertices. I want to take one that has exactly 2 edges to it, so when I remove it will fit.
Just to be clear, I started my proof by saying that if G is a tree then $m=n-1$ and it's all good.
How can I show that exists a vertice with 2 edges?

• Can I say that since there is a circle in $G$, one of it's vertices has to be with 2 edges? otherwise the "middle" edge of all of the has to intersect each other in the center of the circle or to meet with a defferent vertice in the middle (contradicting it's outerplaner)? Jun 29 '15 at 16:53

If the graph is $K_1$ it is false since $m=0$ and $n=1$.

Let $n\geq 2$: If the graph is a tree it has $n-1\leq 2n-3$ edges.

We suppose the graph is not a tree:

If you add the number of edges each face has you get $2m$. This sum is at least $3(f-1)+n$ since the inner faces have at least $3$ edges and the outer face has at least $n$ edges (since the outer edges form a connected graph that is not acyclic). So $2m\geq3f+n-3\implies 3f \leq 2m+3-n\implies f\leq\frac{2m+3-n}{3}$.

Now we use Euler's formula:

$2=n+f-m\leq n+\frac{2m+3-n}{3}-m\implies 6\leq 3n+2m+3-n-3m\implies m\leq2n-3$

• That is another way to do it. Thanks. But how can I show that there is a vertice with 2 edges in $G$? If you can reffer to my comment above. Jun 29 '15 at 16:58
• A vertex with degree exactly $2$ in $G$? Jun 29 '15 at 16:59
• A vertex with degree exactly 2 in G... Jun 29 '15 at 16:59
• that is not necessarily true look at this picture upload.wikimedia.org/wikipedia/commons/thumb/7/7d/… Jun 29 '15 at 17:01
• For trees $m=n-1$ as I said, and the case above is only for $G$ which are not trees. Jun 29 '15 at 17:04