in Others edited by
2,044 views
0 votes
0 votes

A tree has $2n$ vertices of degree $1$, $3n$ vertices of degree $2$, $n$ vertices of degree $3$. Determine the number of vertices and edges in tree.

  1. $12, 11$
  2. $11, 12$
  3. $10, 11$
  4. $9, 10$
in Others edited by
2.0k views

2 Answers

0 votes
0 votes
Here we use the property that sum of degrees of all vertices is twice the number of edges.

For a tree with x number of vertices, we have x-1 edges.

Total number of vertices=2n+3n+n=6n

sum of degrees=2n*1+3n*2+n*3=11n

which is equal to twice number of edges i.e., 2*(6n-1)

So, 11n= 2*(6n-1)

11n=12n-2

So n=2.

Total number of vertices =6n=12

Total number of edges =12-1=11
0 votes
0 votes

According to Handshaking-Lemma  Sum of the degree of all the vertices is even. 

that is $ \sum_{ i =1 }^n \text{degree} (v_i)=2e$

Note: Degree of vertices = the number of edges incident with it.

Given: 1) Number of vertices with $d(1)=2n$

            2) Number of vertices with $d(2)=3n$

            3) Number of vertices with $d(3)=n$

The number of edges is not given in question but we know that a tree $T$ having $n$ vertices contain $(n-1)$ edges.

Here total number of vertices $(V) =2n+3n+n=6n \qquad\dots\dots(i)$

Total number of edges $(E) = (6n-1) \qquad \dots\dots (ii)$ 

$\because$  Sum of the degree of all vertices $=2*$ number of edges

$\implies 2n*1+3n*2+n*3= 2*(6n-1)$

$\implies 2n+6n+3n=12n-2$

$\implies 11n=12n-2$

$\implies n=2$

Put $n=2$ in eq $(i),(ii)$,we get

Total number of vertices $(V)= 6*2=12$

Total number of edges $(E)= 6*2-1=11$

Option $(A)$ is correct.

Ref:1) Gate 2004

      2)  Gate 2017

Related questions