in Graph Theory retagged by
6,431 views
3 votes
3 votes
If G is a planar graph  with 35 regions each of degree 6 the no of vertices are

a) 70 b) 80 c) 72 d) 62

What does degree of a region specify here?
in Graph Theory retagged by
6.4k views

2 Answers

7 votes
7 votes
Best answer

If f is any face, then the degree of f (denoted by deg f) is the number of edges encountered in a walk around the boundary of the face f

No. edges = no. of region*(deg/2) (since each edge is part of exactly 2 regions in a planar graph and hence contributes 2 to the sum of degrees)


We have Euler's formula for planar graph

$n - e + f = 2$, where $n$ is the no. of vertices, $e$ is the no. of edges and $f$ is the no. of faces (regions in planar representation)

And we have $2e = 6f = 6 \times 35 = 210 \\ \implies e = 105$.

Now, $n = 2 + 105 - 35 = 72$.
 

selected by

3 Comments

No of edges*2 = Sum of degrees of vertices 

then how  No of edges*2 = degree* region...

What does degree of a region mean...?

0
0
0
0
0
0
0 votes
0 votes
r=e-v+2

35=e-v+2

e-v=33

35*6=2*e

e=105

e-v=33

105-33=v

v=72