in Graph Theory retagged by
24,511 views
32 votes
32 votes
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_______________.
in Graph Theory retagged by
24.5k views

12 Comments

plz verify @arjun sir i m assuming no of face is x then total no of edge =3x then use the eular formula V-E+R=2

=> 10-3x+x=2 (bcz each face act as a region) so get x=8 then they ask no of edge so it will be 3x=24 ans
2
2
is planar graph there in syllabus of gate 2019 ?
4
4

@rajan

Plz check ur solution:

10-3x+x =2

X = 4 ( not 8)

1
1
edited by
Isn’t this in the syllabus of Gate 2021??

Why it is tagged out of syllabus?
1
1
Yes, someone needs to remove these tags
0
0

If you are wondering why E = $\frac{3F}{2}$

In the question it is given “the number of edges on each face is 3”, it means that if we take any face it will be surrounded by 3 edges, now lets say there are 10 faces, so according to question 10*3 = 30 edges must be there.

One more thing is that one single edge divides the faces in two parts (Draw any simple figure you’ll understand), meaning one edge is shared by 2 faces. Acc to our hypothetical example $\frac{30}{2}$=15 edges.

 

Coming back to the actual question let number of faces be F so we have 3F edges, and since each edge is shared by two faces we have 3F/2, hence E = $\frac{3F}{2}$

0
0

@endurance1 , I understand using this but why can't we solve using E = 3 x F ?

so in Euler’s theorem : 

N + F = E + 2

N + F = 3F + 2

if we do using this method we don't get  24.

0
0
This is in the syllabus now,
1
1

@Arjun sir remove the tag “Out of syllabus”.

0
0
Planarity is in syllabus?
0
0

@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

 

3
3

Possible configuration based upon the given conditions. Edges = 24

1
1

9 Answers

51 votes
51 votes
Best answer

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

selected by
by

4 Comments

edited by

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

 

1
1
nice one
0
0

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 

7
7
36 votes
36 votes

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.

1 comment

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.

0
0
11 votes
11 votes
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.

1 comment

GooD Explanation
0
0
3 votes
3 votes

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.

 

 

 

 

1 comment

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

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