What is the size of the smallest MIS (Maximal Independent Set) of a chain of…

Answer: 3

Explanation:

A maximal independent set (MIS) is an independent set that cannot be extended by adding any other vertex. For a path (chain) of n vertices, the smallest possible size of a MIS is at least ceil(n/3), and this bound is achievable.

• Lower bound (at least ceil(n/3)): Partition the path into consecutive disjoint blocks of three vertices (1–3, 4–6, 7–9). In any MIS, each block must contain at least one chosen vertex; otherwise the middle vertex of that block could be added without violating independence, so the set would not be maximal. Therefore you need at least one vertex per block, giving at least ceil(9/3)=3 vertices.

• Construction (shows bound is tight): Number the vertices 1 through 9 along the chain and choose vertices 2, 5, and 8. These three are pairwise non-adjacent (so the set is independent), and every vertex not chosen has a neighbor in the chosen set (so the set is maximal). Thus a MIS of size 3 exists.

Conclusion: Combining the lower bound and the construction, the smallest size of a maximal independent set for a chain of nine nodes is 3.