<p>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.</p>

CC BY-SA 3.0
2014-11-27T16:16:35.400Z
Is there such a simple bound that takes into account the number $m$ of edges in the graph? If $I(n,m)$ denotes the maximal number of independent sets in a graph with $n$ vertices and $m$ edges, we have $I(n,0)=2^n$, $I(n,n(n-1)/2)=n+1$ and $I(n,1)=3\cdot 2^{n-2}$ (if I made no mistake). Do we have a closed form formula for $I(n,m)$?
Bruno
CC BY-SA 3.0
2014-11-27T12:20:07.813Z
2014-11-27T12:20:07.813Z
Tom van der Zanden
<p>If $I(n,m)$ denotes the maximal number of independent sets in a graph with $n$ vertices and $m$ edges.</p>

<p>$I(n,n-1) = 2^{n-1}+1$ is achieved by a star (should be easy to prove, start by proving that any graph with a matching of size $3$ has at most $3^3\times 2^{n-6}$ independent sets, then show that we can not have two node disjoint paths of length $3$ and no induced path of length $4$, the only remaining graph will be the star).</p>

<p>Let $k(n,m)$ be minimum number such that $k(k-1)/2 + k(n-k) &gt; m$. Then there exit graphs with $n$ nodes and $m$ edges having $2^{n-k}+k$ independent sets. Namely an independent set of size n-k and k universal vertices. I think this is close to optimal, hence:</p>

<p>$$I(n,m) \ge 2^{n-k(n,m)}+k(n,m)$$</p>

<p>A more precise bound can be derived from David R. Wood's study of number of cliques,<a href="http://arxiv.org/pdf/math/0602191v4.pdf" rel="nofollow">On the Maximum Number of Cliques in a Graph</a> </p>

CC BY-SA 3.0
2014-11-28T07:58:18.990Z
2014-11-28T23:26:43.763Z
2014-11-28T23:26:43.763Z
Martin Vatshelle
<p>What is the tightest upper bound known for the number of independent sets in a graph?</p>

CC BY-SA 3.0
2014-11-28T09:44:19.363Z
Upper bound in terms of what parameters of the graph?
David Richerby
CC BY-SA 3.0
2014-11-29T13:34:48.167Z
@David: I think this question is worthwhile even without specifying the parameters, since there are only two that are typically considered (vertices and vertices/edges); this is reflected in the answers.
András Salamon
<graph-theory><graph-algorithms><counting-complexity><upper-bounds><extremal-combinatorics>
Upper bound for number of independent sets
chtenb
# Upper bound for number of independent sets

(Asked by: username_0 on 2014-11-27)

What is the tightest upper bound known for the number of independent sets in a graph?

**Tags:** graph-theory, graph-algorithms, counting-complexity, upper-bounds, extremal-combinatorics
> **Comments:**
> **username_1**: Upper bound in terms of what parameters of the graph?  
> **username_2**: @David: I think this question is worthwhile even without specifying the parameters, since there are only two that are typically considered (vertices and vertices/edges); this is reflected in the answers.  

---

## 2 answers

### Answer by username_3 on 2014-11-27. Score: 5 | Accepted answer

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.

> **Comments:**
> **username_4**: Is there such a simple bound that takes into account the number $m$ of edges in the graph? If $I(n,m)$ denotes the maximal number of independent sets in a graph with $n$ vertices and $m$ edges, we have $I(n,0)=2^n$, $I(n,n(n-1)/2)=n+1$ and $I(n,1)=3\cdot 2^{n-2}$ (if I made no mistake). Do we have a closed form formula for $I(n,m)$?  

---

### Answer by username_5 on 2014-11-28. Score: 3

If $I(n,m)$ denotes the maximal number of independent sets in a graph with $n$ vertices and $m$ edges.

$I(n,n-1) = 2^{n-1}+1$ is achieved by a star (should be easy to prove, start by proving that any graph with a matching of size $3$ has at most $3^3\times 2^{n-6}$ independent sets, then show that we can not have two node disjoint paths of length $3$ and no induced path of length $4$, the only remaining graph will be the star).

Let $k(n,m)$ be minimum number such that $k(k-1)/2 + k(n-k) > m$. Then there exit graphs with $n$ nodes and $m$ edges having $2^{n-k}+k$ independent sets. Namely an independent set of size n-k and k universal vertices. I think this is close to optimal, hence:

$$I(n,m) \ge 2^{n-k(n,m)}+k(n,m)$$

A more precise bound can be derived from David R. Wood's study of number of cliques,[On the Maximum Number of Cliques in a Graph](http://arxiv.org/pdf/math/0602191v4.pdf)


---

