Dark Mode

20,468 views

27 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_______________.

@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

2

49 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

edited
Jul 24, 2020
by Hradesh patel

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

0

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

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

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.

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.

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.