Define a graph to be $k$-Hamiltonian if there exist $k$ simple cycles in the graph that together cover all of the vertices. Use inclusion-exclusion to design an algorithm that tests whether a graph is $3$-Hamiltonian. What is the running time of your algorithm?
Recall that the fast zeta transform takes a function $f(S)$ from sets to real numbers as input, and produces as output a function $\hat f(S)=\sum_{T\subset S} f(T)$. Describe an algorithm that takes $\hat f$ as input and produces $f$ as output.
How many perfect matchings are there in a four-dimensional hypercube? (This is a bipartite graph with 16 vertices, which can be associated with the four-bit binary numbers in such a way that two vertices are adjacent if and only if their numbers differ in a single bit. Computational solutions are encouraged but not required.)