 Solution

ID: 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 are

{B, D, F} and {B, E, F}, α (G) = 3.

{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

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

 New to topics? Read the docs here!