  We show that the number of independent sets in an N-vertex, d-regular graph
is at most (2^{d+1} - 1)^{N/2d}, where the bound is sharp for a disjoint union
of complete d-regular bipartite graphs. This settles a conjecture of Alon in
1991 and Kahn in 2001. Kahn proved the bound when the graph is assumed to be
bipartite. We give a short proof that reduces the general case to the bipartite
case. Our method also works for a weighted generalization, i.e., an upper bound
for the independence polynomial of a regular graph.
