gatebook

Question

What is order means here and how to solve this?

Comments

I think here order means the number of vertices in the given graph.

Answer =  No of vertices of degree 3 = (n-2) / 2 ???

---

then what is the meaning of degree??

---

sum of degree = 2*# of edges

3*n₃ + 1*(n-n₃) = 2*(n-1) // since tree with n vertices has n-1 edges.

n₃ = (n-2)/2

---

In graph terminology size = number of edges and order = number of vertices.

Answer 1

Order means number of vertices in a graph and size means number of edges in a graph.

So we have number of vertices  =   n

Let number of vertices of degree 3  = x

  So number of vertices of degree 1  =  n - x

Also as the graph given is a tree and we know :

In tree , number of edges = number of vertices - 1

Now applying handshaking lemma , we have :

         Sum of degree of vertices   =   2 * Number of edges

 ==>  3x + (n - x)                         =   2 * (n - 1)   =   2 n - 2

 ==>  2x + n                                =   2n - 2

 ==>  x                                        =   (n-2) / 2

 Hence number of vertices of degree 3  =  x   =   (n-2) / 2