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}.
$$