The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+6 votes
284 views
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.
in Graph Theory by Boss (18.1k points) | 284 views
+1

V - E + r = 2

4r <= 2E

using both, we will get E<= 26

0
Ok so length =4 and greater will work.

Ryt??
0
yes..
+1
My bad I was taking it as 5. By the way thanks.
0
For a connected planar simple graph with n vertices and m edges and no triangles (cycles of length 3).

m $\leq$ 2 * n - 4

1 Answer

+2 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


 

by Boss (43k points)
selected by
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.

https://www.cs.sfu.ca/~ggbaker/zju/math/planar.html

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

0
I did it as:-

Degree of each region = 4

Summation(Degree of each region) = 4r

where r is the number of regions

And Also Sum of degree of each region is = 2|E| equating all together

r = |E|/2

putting in Euler's formula:-  v - e + r = 2

we get 2v - 4 = e

e = 2*15-4

e = 26.
0
Is planar graph part of the syllabus?
0
@krish Syllabus isn't fully defined. So it's better to study its basics. In 2015 or 2016 there was a question in GATE on the chromatic number of a planar graph.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,362 questions
55,786 answers
192,410 comments
90,918 users