1,778 views
7 votes
7 votes
Graph G(V,E) is a connected planar graph with no cycle of length less than 4 edges, if |V| = 15 then maximum value of |E| is:

The answer given is 26.

1 Answer

Best answer
5 votes
5 votes

In a connected Plannar graph
1. |E| <= 3*|V| - 6, max number of possible edges
2. |E| <= 2*|V| - 4, if no circuit of length 3, or degree of each region is >=4
3. |V| + |R| = |E|+2 , |R| number of regions
4. k*|R| <= 2*|E|, where k is the at least degree of a region

|V|=15,
Max edge possible |E| = 3*15-6 <= 39 ( max number of possible edges, if no condition other than graph is connected & planar)

In our question
4*|R| <=2*|E|
|E| = 2*|R|
V + R = E + 2
15 + E/2 = E+2
13 = E/2
|E| = 26

(or) 

we can apply direct formula here as the degree of each region is >=4, so

e = 2*v -4 = 2*15-4 =26


 

selected by

Related questions

0 votes
0 votes
0 answers
1
3 votes
3 votes
0 answers
2