[Math] Graph Theory: Number of vertices in a tree.

discrete mathematicsgraph theorytrees

– Background Information:

I am studying graph theory in discrete mathematics. I have come across a question and a solution (provided by my professor). However, I cannot understand the solution clearly, I need clarification, thanks.

– Question:

Let T be a tree with an average degree a. Determine the number of vertices in T.

– Professor's solution:

Note that the sum of the degrees of the nodes of T is twice the number of edges. But a tree on n nodes will have n – 1 edges. Thus, 2(n – 1) = n*a which implies n = 2 / (2 – a).

– Logical Questions:

  • Consider the below example graph (Note: not part of the original question).

enter image description here

  1. I understand there are n = 6 nodes, and n – 1 edges, so 5. The sum of degrees is 10. How do we get the average degree a?

  2. Look at the provided solution, there is an equation 2(n – 1) = n*a, how do we get n = 2 / (2 – a) out of it? I have tried it, but it didn't work.

My thinking:

  1. I think average degree is sum of degrees 10 divided by number of nodes 6, so almost 1. Am I right?

  2. Also some algebra, 2(n – 1) – n*a => 2n – 2 = n * a => n = (n*a +2) / 2

Considering the equation n = 2 / (2 – a), where the average degree is 1 because sum of degrees / num nodes, I get n as n = 2 / (2-1) so n = 2. I know this answer is definitely wrong, please explain me how I need to think to solve this question.

Best Answer

The average degree isn't necessarily an integer, in your case it would be $\frac{10}{6} = 1.666667$.

For the second part move all the terms containin $n$ on one side and you will get $(2-a)n = 2$. Now divide both sides by $2-a$, which isn't zero as the average degree in a tree is always less than $2$.

Related Question