# Each regional of a maximal planar graph is a triangle

Show that every region of a maximal planar graph is a triangle.

• A planar graph G is called maximal planar if the addition of any edge to G creates a nonplanar graph.

Will this proof use the theorem that states that if G is planar with $n \ge 3$ and $e$ edges, then $e \le 3n-6$. Furthermore, if the equality holds then every region is bounded by three edges.

I'm not sure how to show that for every single region, this claim will be true.

• If a boundary is not a triangle you can add a chord to get a bigger planar graph. That's the intuitive reason at least. Feb 5 '16 at 1:48

To prove your result, observe that it isn't true for $n=1$ and $n=2$ so let $n\geq 3$. Assume to the contrary that there is a maximal planar graph $G=(V,E)$ embedded in the plane with a region that is not a triangle.
Then the region that is not a triangle must have three consecutive vertices on its boundary, say $v_1,v_2$ and $v_3$ where $v_1v_2,v_2v_3\in E$ but $v_1v_3\not\in E$. then we may safely add the edge $v_1v_3$, contradicting maximality. Thus, every region of a maximal planar graph on $n\geq 3$ vertices is a triangle.