Question

Let G be a simple graph. G is said to be maximal planar if it is planar and the addition of any new edge to G results in a (simple) non-planar graph. Examples of maximal non-planar graphs are K4 , K5 minus an edge, and K3,3 minus an edge.

(a) Show that a maximal planar graph is connected.

(b) Show that a maximal planar graph of order ≥3 has no bridges.

(c) Show that every face of a maximal planar graph of order ≥3 is bounded by a triangle.

Answer 1

(a)

If an edge e of a maximal planar graph is in exactly two triangles then G/e is also maximal planar. (Since G/e has exactly three fewer edges.)

If G is a maximal planar graph with n≥4 vertices then there are at least n such edges. (Induction on n.)

Let G be a maximal planar graph with at least four vertices. Assume that there are vertices u,v such that G−{u,v} is disconnected. Let X be one component of G−{u,v} and let Y be another.

Contract edges of G until we're left with just u and v along with one vertex of X and one vertex of Y.

Since there are now only four vertices, we must be left with K4. But then removing u and v can't disconnect the graph, so we have a contradiction.

Hence a maximal planar graph is connected always.

c)

Observe that it isn't true for n=1 and n=2 so let n≥3.

Assume to the contrary that there is a maximal planar graph G=(V,E) embedded in the plane with a face 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 face must be a cycle.

Then the face that is not a triangle must have three consecutive vertices on its boundary, say and where but . then we may safely add the edge , contradicting maximality. Thus, every face of a maximal planar graph on n≥3 vertices is a triangle.

I am not very sure in part b). So I am unable to answer this part.

Ask if any quarries. Thank you