Share
Explore BrainMass

Prove that a planar graph of order n>=3 and size m is maximal planar if and only if m=3n-6

Prove that a planar graph of order n>=3 and size m is maximal planar if and only if m=3n-6

What does maximal planar graph mean?

Solution Preview

A graph G is maximal planar graph means that G is planar, but if we add one more edge between a pair of non-adjacent vertices, the resulting graph is not planar.

We prove

(1) If G is a planar graph of order n>=3 and size m is maximal planar , then m=3n-6

Proof. Denote by r the number of regions of G. In G the boundary of ...

Solution Summary

It is proven that a planar graph of order n>=3 and size m is maximal planar if and only if m=3n-6.

$2.19