Suppose we have a graph $G(V,E)$ [![enter image description here][1]][1] [1]: https://i.sstatic.net/u1bIH.png What is the number of independent sets in graph of this type? I have an idea to use reccurence $$|G|=|G\backslash \{v\}|+|G\backslash n(v)|$$ where $|G|$ is the number all possible independent sets of graph G, $v$ is an arbitrary vertex, and $n(v)$ is a set of all vertex's joined to $v$ and $v$ itself. But may be there some better ideas or results?