Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Functional programming, design and analysis of algorithms / 6 / c / Solution

Three examples of independent sets are $\{A,C\}$, $\{B,D\}$ and $\{C,E\}$: none contains both endpoints of an edge. The maximum independent sets areThe triangle on $\{A,D,E\}$ contributes at most one vertex, and the path on $\{B,C,F\}$ contributes at most two, giving the upper bound three. Both displayed sets attain it. A three-element choice cannot use $A$, since that excludes $B$ and leaves at most one of the adjacent vertices $C,F$. Consequently it must use $D$ or $E$, together with both $B,F$; these are the only two choices. In particular, the maximum independent set is not unique.

Highlighted vertices give the two possible optimal choices. The third side of the left triangle rules out choosing both $D$ and $E$.