Three examples of independent sets are , and : none contains both endpoints of an edge. The maximum independent sets areThe triangle on contributes at most one vertex, and the path on contributes at most two, giving the upper bound three. Both displayed sets attain it. A three-element choice cannot use , since that excludes and leaves at most one of the adjacent vertices . Consequently it must use or , together with both ; these are the only two choices. In particular, the maximum independent set is not unique.
The two maximum independent sets of size three
. Details. No. A tree consisting of a single edge has the two maximum independent sets and . Each has size one, and neither can be enlarged because are adjacent. Thus even a two-vertex tree gives a counterexample to uniqueness.
