Number of Graphs on n vertices without isolated vertices

[dobry_den]

Homework Statement

What is the number of graphs on n vertices (V = {1,2,3,...,n} with no isolated vertices?

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!

 

[mighty2000]

I think your approach is correct and your solution looks mathematically sound. However, I would suggest adding a brief explanation or proof of why your approach is valid and how you arrived at your final equation. This can help others understand your solution and also showcase your understanding of the problem. Additionally, you may want to consider providing an example or two to demonstrate your solution. Overall, great job!