Let T be a nontrivial tree. Determine the minimum possible number of maximal indepen-dent sets in T . Determine all the possible structure of T achieving the minimum number.

문제출처

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