The Gateway to Computer Science Excellence
+17 votes
5.2k 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.2k points)
retagged by | 5.2k 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 ?

3 Answers

+37 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 (425k 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
+24 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.7k points)
0
GooD Explanation

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,645 questions
56,551 answers
195,704 comments
101,558 users