The Gateway to Computer Science Excellence
+18 votes
5.6k views
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 by Boss (30.7k points)
retagged by | 5.6k views
+1
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
+4
is planar graph there in syllabus of gate 2019 ?

4 Answers

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

by Veteran (430k points)
selected by
+4

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

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

Answer is same that is 24.

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

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

+8

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

0
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.
+4

The graph looks like this. 

GRAPH

0

Can we use the formula :

e <= 3n-6 for connected planar graph

for n=10 

e <= 30-6= 24

Please correct if wrong approach.

0
Arjun sir, in this question are we talking about only bounded regions??? Because as I know unbounded regions always have degree 0
+27 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.

by (155 points)
+10 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.
by Active (1.8k points)
0
GooD Explanation
0 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.

 

 

 

 

by (475 points)
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
50,737 questions
57,258 answers
198,087 comments
104,737 users