Deletion-contraction
P(G, k) = P(G-e, k) - P(G/e, k). Take any edge, either don't use it (delete) or force endpoints same color (contract).
Advertisement
Base cases
Empty graph on n vertices: k^n. Tree on n: k(k-1)^(n-1). Complete graph K_n: k(k-1)(k-2)…(k-n+1).
Advertisement
Complexity
Exponential in general (#P-hard). Polynomial only for structured graphs.