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

This is a "planner" graph with 10 vertices and each face has only 3 edges.

---

I'm not able to visualize the graph. How many edges are you getting?

---

Answer is same that is 24.

---

@Arjun, will questions like this depending on concepts of Planar Graphs (faces etc) will it be asked ? in GATE 2016 ?

---

@Arjun"number of edges on each face is three"

f=3e I am getting

how r u getting e=3f ?

Could u give me a simple example to understand this line?

---

number of edges on each face is three, 

max edges = 2e in any graph

here 3 faces have 3 edges each so

3f= 2e

e= 3f/2

---

For every face we need 3 edges. But en edge serves two faces (face - edge - face). So, for f faces we get 3f/2 edges.

---

The graph looks like this. 

---

Can we use the formula :

e <= 3n-6 for connected planar graph

for n=10 

e <= 30-6= 24

Please correct if wrong approach.

---

Arjun sir, in this question are we talking about only bounded regions??? Because as I know unbounded regions always have degree 0

---

@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. 😲