Question

A simple planar graph to which no edges can be added without destroying its planarity (while keeping the graph simple of course) is called a maximal planar graph.prove that the every region in a maximal planar graph in a triangle​

Answer 1

Step-by-step explanation:

mark me as brainlist

plz be my follower

To prove your result, observe that it isn't true for n=1n=1 and n=2n=2 so let n≥3n≥3. Assume to the contrary that there is a maximal planar graph G=(V,E)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 v1,v2v1,v2 and v3v3 where v1v2,v2v3∈Ev1v2,v2v3∈E but v1v3∉Ev1v3∉E. then we may safely add the edge v1v3v1v3, contradicting maximality. Thus, every region of a maximal planar graph on n≥3n≥3 vertices is a triangle