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?

  • $\begingroup$ 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. $\endgroup$ Oct 21 '20 at 21:07
  • $\begingroup$ @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, $\endgroup$ Oct 21 '20 at 21:20
  • 1
    $\begingroup$ @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. $\endgroup$ 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.

![enter image description here

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.

  • $\begingroup$ Thank you! So I can finish the proof by removing the vertex of degree 2 to get a smaller maximal outerplanar graph (as Randy suggested). By the induction hypothesis this graph has 2(n-1) - 3 edges. If I put the vertex back I get two edges more which would be 2(n-1) - 3 + 2 = 2n-3 edges. Is this reasoning correct? $\endgroup$
    – Ahiru
    Oct 21 '20 at 21:46
  • $\begingroup$ @Ahiru Yeah, that works ^^ $\endgroup$ Oct 22 '20 at 9:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.