0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Matt Samuel Feb 5 '16 at 1:48
2
$\begingroup$

you don't need that result(actually usually that result is proved USING the fact that maximal planer graphs have only triangular regions!)

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.

Clearly the graph is connected, for otherwise we could add any edge between the outer-boundary of any two components. Furthermore, the boundary of each region is a cycle. To see this, first consider the case where the boundary is acyclic. then it is a tree with at least three vertices. Adding any edge to a tree on three or more vertices preserves planarity, so it couldn't be maximal. now assume that the boundary contains a cycle but is not solely a cycle. Then we have a cycle with trees branching off the cycle. since a tree contains at least two leaves, there is one leaf of the tree that is not in the cycle. An edge can be added from this leaf to any vertex in the cycle that is not also in the tree in question, contradicting maximality. Thus the boundary of each region must be a cycle.

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.

$\endgroup$
1
$\begingroup$

Take a region which is not a triangle. What is your definition of region? Can you add an edge?

Hope that helps,

$\endgroup$

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.