**V - E + r = 2**

**4r <= 2E**

using both, we will get E<= 26

The Gateway to Computer Science Excellence

+6 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.

The answer given is 26.

+3 votes

Best answer

**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

0

|R| <= 2*|V| - 4, max number of regions

It will be E<= 2V -4 when no cycle of left three i.e. degree of region is atleast 4.

0

yes anu, what you said is correct. but i read it somewhere, anyways i am correcting it in my answer because i didn't find any source to confirm that |R|<=2*|V|-4

0

Check corollary 2 here, to proof E <= 2V - 4, When there is no triangle in the graph.

http://www.personal.kent.edu/~rmuhamma/GraphTheory/MyGraphTheory/planarity.htm

52,218 questions

59,890 answers

201,084 comments

118,128 users