# Number of Graphs on n vertices without isolated vertices

1. Dec 18, 2007

### dobry_den

1. The problem statement, all variables and given/known data
What is the number of graphs on n vertices (V = {1,2,3,...,n} with no isolated vertices?

3. The attempt at a solution
I defined $$A_{i}$$ to be a set of graphs with the vertice "i" is isolated:

$$A_{i} = \left\{G=\left(V,E\right); \text{vertice "i" is isolated}\right\}$$

Then I used the Inclusion-Exclusion Principle to count all the "bad" graphs, i.e. those with any of the vertices isolated:

$$\left|\bigcup_{i=1,2,..,n}A_{i}\right| = \sum_{k=1}^{n}{(-1)^{k-1}\binom{n}{k}\cdot2^{\binom{n-k}{2}}$$

The last thing to do is to subtract this from the number of all graphs:

$$2^{\binom{n}{2}} - \sum_{k=1}^{n}{(-1)^{k-1}\binom{n}{k}\cdot2^{\binom{n-k}{2}} = \sum_{k=0}^{n}{(-1)^{k}\binom{n}{k}\cdot2^{\binom{n-k}{2}}$$

Do you think it's correct? Every help would be greatly appreciated!

Last edited: Dec 18, 2007