Question

A maximal plane graph is a plane graph G = (V, E) with n ≥ 3 vertices such that if we join any two non-adjacent vertices in G, we obtain a non-plane graph.

a) Draw a maximal plane graphs on six vertices.

b) Show that a maximal plane graph on n points has 3n − 6 edges and 2n − 4 faces.

c) A triangulation of an n-gon is a plane graph whose infinite face boundary is a convex n-gon and all of whose other faces are triangles. How many edges does a triangulation of an n-gon have?

Answer 1

IF YOU HAVE ANY DOUBTS COMMENT BELOW I WILL BE TTHERE TO HELP YOU..ALL THE BEST..

AS FOR GIVEN DATA.

(b): Let G be a planar graph with n vertices and F faces and E number of edges .

Now , The boundary of every faces is a triangle , and each edge is on the boundary of two faces.

Therefore , if the number of edges on the boundary of a face is summed over all faces , the result will be 3F .

On the other hand, such a sum considers each edge twice .

So , 3F = 2E , i.e. , F=(2E)/3 and E=(3F)/2. ............... (i)

Applying Euler's formula ,

i.e., If a connected plane graph G has V vertices , E edges and F faces , then ,

.  V-E+F = 2.

We obtain the desired results;

V - E + F = 2.

=> n - E + F = 2. ................ (ii)

Now , from (i) we have ,

n - E + (2E/3) = 2

=> 3n - 3E + 2E = 6

=> 3n - E = 6

=> E=3n-6

Similarly ,

From (i) and (ii) , we have ,

n - E + F = 2

=> n - (3F/2) + F = 2

=> 2n - 3F + 2F = 4

=> 2n - F = 4

=> F=2n-4.

(c) : Let R (n) be a graph whose vertices are every distinct triangulation of the n-gon , and whose edges represent the ability to get from one triangulation to another via diagonal flip. Let N_n be the number of vertices of R (n) .

Since , Number of edges of an n-gon is (n-3) .

Therefore , there are (n-3) flips that can be performed on each triangulation, which means that the degree of each vertex of R(n) =(n-3) , which means that R(n) is an (n-3)-gon graph.

Thus , Number of edges of R(n) is {N_n × (n-3)}/2.  ( 2 in denominator is because each edge was considered twice).

I HOPE YOU UNDERSTAND..

PLS RATE THUMBS UP..ITS HELPS ME ALOT..

THANK YOU...!!