The number of independent sets in a graph with small maximum degree

David Galvin, Yufei Zhao

Let $\mathrm{ind}(G)$ be the number of independent sets in a graph $G$. We show that if $G$ has maximum degree at most $5$ then $$ {\rm ind}(G) \leq 2^{{\rm iso}(G)} \prod_{uv \in E(G…