문제출처
광주과학기술원(GIST) 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 4
Solution
1. Let's consider a graph $G$ such that $|E_G| < |V_G|$, where $|E_G|$ is the number of edges in $G$, and $|V_G|$ is the number of vertices in $G$.
2. Suppose that $G$ has connected components $G_1, G_2, \dots, G_k$. Each $G_i$ is a connected subgraph. If $G_i$ is not a tree, then $G_i$ must have a cycle.
3. A key property of a tree is that $|E| = |V| - 1$. To add a cycle to a tree, we need at least one additional edge. Thus, for each $G_i$, we have $|E_{G_i}| \geq |V_{G_i}|$.
4. The total number of edges $|E_G|$ is the sum of the edges in each connected component:
$$
|E_G| = \sum\limits_{i=1}^k |E_{G_i}|.
$$
5. Since $|E_{G_i}| \geq |V_{G_i}|$ for each $G_i$, we have:
$$
|E_G| = \sum\limits_{i=1}^k |E_{G_i}| \geq \sum\limits_{i=1}^k |V_{G_i}|.
$$
6. The total number of vertices $|V_G|$ is the sum of the vertices in each connected component:
$$
|V_G| = \sum\limits_{i=1}^k |V_{G_i}|.
$$
7. Combining these results, we get:
$$
|E_G| = \sum\limits_{i=1}^k |E_{G_i}|
\geq \sum\limits_{i=1}^k |V_{G_i}|
= |V_G|.
$$
8. Thus, $|E_G| \geq |V_G|$.
9. This contradicts the assumption that $|E_G| < |V_G|$. Hence, at least one connected component must be a tree.