= 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> are
$$
\boxed{\{B,D,F\}\quad\text{and}\quad\{B,E,F\},\qquad \alpha(G)=3.}
$$
The 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, \b[the maximum independent set is not unique].
\Image[/past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2015/functional-main-2015-independent-sets.png]
{title=The two maximum independent sets of size three}
Highlighted vertices give the two possible optimal choices. The third side of the left triangle rules out choosing both $D$ and $E$.
Back to article page
