Prove or disprove: Every graph with fewer edges than vertices has a component that is a tree.

문제출처

광주과학기술원(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.