GATE CSE 2015 Set 1 | Question: 54

Question

Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is_______________.

Comments

Planarity is in syllabus?

---

@Arjun Sir, although not explicitly mentioned in the syllabus, questions have appeared from planarity recently.

Eg: GATE CSE 2021 Set 1 | Question: 16 - GATE Overflow for GATE CSE

 

---

Possible configuration based upon the given conditions. Edges = 24

Answer 1

By Euler formula for connected planar graph,

$n - e + f = 2$

$10 - 3f/2 + f = 2 $ (An edge is part of two faces)

$f/2 = 8$

$f = 16$

$e = 3f/2 = 24$

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

Comments

@Arjun sir, 

in the question given:

No of edge of every face is three

means  f= 3e (wrong)

   e  = 3 f ( right)

i also know that every edge cover 2 faces.

e= 3f/2

plz check sir ...I am going right or wrong...

 

---

nice one

---

Each face has 3 edge...It means 

1 face =  3 edge

=>  f Face =  3*F edge

As each edge will be a Part of 2 different faces we have to divide the number of edges by 2.

=> f Face = (3*f)/2 edge 

Now use formula n-e+f=2 

Answer 2

Gven 

no of vertices = 10

The no of edges on each face = 3

Let the no of vertices be 'n' ,no of edges be 'e' , the no of regeions ( faces) be ' r ' .

But 

The sum of the degrees of the regions ( faces ) = 2( no of edges)

d(R1) + d(R2) + d(R3) +..............(r times) = 2e

3+3+3+......................(r times )= 2e

3r = 2e

r = 2e/3

By euler's formula we have 

n - e + r = 2

10 - e + 2e/3 = 2

10 - e/3 = 2

30 - e = 6

e = 24

The no of edges = 24.

Comments

Hey Mahesh,

The sum of the degrees of the regions ( faces ) = 2( no of edges)

I think you should also mention that this theorem is valid for the planar graph only.

Check out more on Planar Graph.

Answer 3

By Eulers Formula

N-e+f=2

Where N is the number of Vertices, e is the number of edges and f is the number of face

Here N=10

and it is given that Number of edges on each faces is three , and Each edge is part of two faces..

So  N-e+f=2 becomes 10-3*f/2+f=2

=>     f=16

Now N-e+f=2 gives e=24

So number of edges in given graph will be 24.

Comments

GooD Explanation

Answer 4

WHOSOEVER Folks drawing the graph like this :

and thinking why the relation   "3R = 2E"  is not satisfying because the open region is not surrounded by 3 vertices. 

In Question, it is clearly mention " number of edges on each face is three".

Just to point out, because it took me 30 min to understand Where I'm wrong while drawing this graph.

 

 

 

 

Comments

Thanks man... After spending 30 minutes and finally finding it out I read this answer. 😲