문제출처
광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 5
Solution
1. In a tree, there are leaf vertices and non-leaf vertices. If we take a maximal independent set that includes a leaf vertex, we can also construct a different maximal independent set that excludes that leaf and includes its neighbor instead.
2. Thus, there are always at least two distinct maximal independent sets in any tree. A tree cannot have exactly one maximal independent set.
3. Let's consider the star graph $K_{1,n}$. We have two maximal independent sets:
- One is the set containing all the leaves.
- The other is the set containing only the central vertex.
$K_{1,n}$ is a tree where the number of maximal independent sets is 2. Since a tree cannot have exactly one maximal independent set, 2 is the minimum possible number.
4. I will check that $K_{1,n}$ is the only tree that has exactly two maximal independent sets.
5. If a tree has at least two internal vertices (vertices with degree 2 or more), it is a non-star tree.
6. If a tree has at least two internal vertices, let them be $u$ and $v$. We can construct at least 3 distinct maximal independent sets:
- One is the set containing $u$ and excluding its adjacent vertices.
- Another is the set containing $v$ and excluding its adjacent vertices.
- The third is the set containing all leaves and excluding all internal vertices.
7. Conclusion: The minimum possible number of maximal independent sets in a tree $T$ is 2, and $K_{1,n}$ is the only possible structure of $T$ achieving this minimum number.