search
Log In
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
21 votes
6.8k 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
retagged by
6.8k 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 ?
0

@rajan

Plz check ur solution:

10-3x+x =2

X = 4 ( not 8)

4 Answers

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

9

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

The graph looks like this. 

GRAPH

1

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

 

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

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

 

 

 

 

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

Related questions

8 votes
3 answers
1
3.3k views
Consider the following C program segment. while (first <= last) { if (array[middle] < search) first = middle + 1; else if (array[middle] == search) found = TRUE; else last = middle - 1; middle = (first + last)/2; } if (first > last) notpresent = TRUE; The cyclomatic complexity of the program segment is_______________.
asked Feb 13, 2015 in IS&Software Engineering makhdoom ghaya 3.3k views
15 votes
1 answer
2
2.3k views
K4 and Q3 are graphs with the following structures. Which one of the following statements is TRUE in relation to these graphs? K4 is a planar while Q3 is not Both K4 and Q3 are planar Q3 is planar while K4 is not Neither K4 nor Q3 is planar
asked Sep 29, 2014 in Graph Theory jothee 2.3k views
15 votes
2 answers
3
3.1k views
Let $\delta$ denote the minimum degree of a vertex in a graph. For all planar graphs on $n$ vertices with $\delta \geq 3$, which one of the following is TRUE? In any planar embedding, the number of faces is at least $\frac{n}{2}+2$ In any planar embedding, the number of faces ... is less than $\frac{n}{2}+2$ There is a planar embedding in which the number of faces is at most $\frac {n}{\delta+1}$
asked Sep 28, 2014 in Graph Theory jothee 3.1k views
11 votes
2 answers
4
2.3k views
Which one of the following graphs is NOT planar? G1 G2 G3 G4
asked Sep 21, 2014 in Graph Theory gatecse 2.3k views
...