Upper bound for number of independent sets What is the tightest upper bound known for the number of independent sets in a graph?
The trivial upper bound of $2^n$ (on a graph with $n$ vertices) is as tight as you can get, since a graph that has no edges does indeed have $2^n$ independent sets.