Let T be a tree with average degree d. In terms of d, determine $n(T)$.

문제출처

광주과학기술원(GIST) 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 4

Solution

1. Since a tree is a connected graph with no cycles, $|E_T| = n(T) - 1$, where $|E_T|$ is the number of edges in $T$.

2. The average degree $d$ is:
$$d = \frac{\sum\limits_{v \in V(T)} d(v)}{n(T)},$$
where $d(v)$ is the degree of vertex $v$, and $V(T)$ is the vertex set of $T$.

3. In a graph, the sum of the degrees of all vertices is equal to $2 \times$ (the number of edges in the graph). Thus,
$$\sum\limits_{v \in V(T)} d(v) = 2 \times |E_T| = 2 \times (n(T) - 1).$$

4. Combining the above equations:
$$d = \frac{2(n(T) - 1)}{n(T)}.$$

5. Therefore,
$$n(T) = \frac{2}{2 - d}.$$