TAOCP 7.1.4 Exercise 14
Number the vertices of the cycle $C_n$ as in the statement, so edges are ${x_i,x_{i+1}}$ for $1 \le i < n$ and ${x_n,x_1}$.
Section 7.1.4: Binary Decision Diagrams
Exercise 14. [M24] [M24] How big, exactly, are the BDDs for (a) all independent sets of the cycle graph Cn, and (b) all kernels of Cn, when n ≥3? (Number the vertices as in (12).)
Verified: no
Solve time: 2m20s
Solution
Number the vertices of the cycle $C_n$ as in the statement, so edges are ${x_i,x_{i+1}}$ for $1 \le i < n$ and ${x_n,x_1}$. Let variables be ordered $x_1,\dots,x_n$ in the BDD.
(a) Independent sets of $C_n$
Let $f(x_1,\dots,x_n)$ be the characteristic function of independent sets of $C_n$, so $f=1$ iff no two adjacent vertices are selected and not both $x_n$