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

An outerplanar graph is a graph that can be drawn as a planar graph where every vertex is incident to the outer region. A maximal outerplanar graph can be drawn such that every vertex is part of a simple cycle where every vertex is part of the outer region and every region inside the cycle is a triangle.

I have to show with proof by induction that for all $$n\geq 2$$ A graph with that drawing has exactly $$2n-3$$ edges.

The base case is easy: $$n=2$$: $$v$$---$$u$$ is the only graph with that drawing. $$1=2\cdot2 -3 =1$$ holds.

The induction hypothesis is stated above.

I can wrap my head around the induction step. I've seen that many induction proofs on graphs deconstruct a graph, use the induction hypothesis on the smaller graph and rebuild the graph to proof that the hypothesis holds. Here I don't see how I can do it. I thought about using rules such as that every new vertex needs to be on the circle and every inner region has to be a triangle which leads to the only possibility of adding 2 edges but I don't use the hypothesis there so it's no proof by induction right?

• Shouldn't $n=3$ be the base case, since for $n=2$ there are no triangles? In the induction step, pick one triangle. This triangle has one edge on the cycle. If $\{u,v,w\}$ are its vertices, and $uv$ is the edge on the cycle, let $z$ be its midpoint. Now add the edges $zu$, $zv$ and $zw$ and delete $uv$. You've deleted 1 and added 3 new edges so in total you have $2n-3+2=2(n+1)-3$ edges. Oct 21 '20 at 21:07
• @RandyMarsh In order for that induction argument to work, you also need to prove every Maxouterplanar graph on $n+1$ vertices arises from one on $n$ vertices by that edge-splitting construction. Which is not necessarily wrong, but it's very much more difficult than necessary, Oct 21 '20 at 21:20
• @BrandonduPreez you are correct, and now that I've though more carefully about it, those maxouterplanar graphs that don't have a vertex of degree $3$ can't be obtained in this way. I thought it was obvious that they'll always have a vertex of degree $3$, but they do not. Oct 21 '20 at 22:37

Hint: Every maximal outerplanar graph of order at least $$3$$ has at least one vertex of degree $$2$$ (if you aren't convinced, draw some examples and then try prove this first), and if you remove this vertex, you still have a maximal outerplanar graph.
The proof from there works in much the same way as Randy Marsh's comment. You remove the vertex of degree $$2$$ to get a maximal outerplanar graph with $$2$$ fewer edges and $$1$$ less vertex.