- #1
dobry_den
- 115
- 0
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 [tex]A_{i}[/tex] to be a set of graphs with the vertice "i" is isolated:
[tex]A_{i} = \left\{G=\left(V,E\right); \text{vertice "i" is isolated}\right\}[/tex]
Then I used the Inclusion-Exclusion Principle to count all the "bad" graphs, i.e. those with any of the vertices isolated:
[tex]\left|\bigcup_{i=1,2,..,n}A_{i}\right| = \sum_{k=1}^{n}{(-1)^{k-1}\binom{n}{k}\cdot2^{\binom{n-k}{2}}[/tex]
The last thing to do is to subtract this from the number of all graphs:
[tex]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}}[/tex]
Do you think it's correct? Every help would be greatly appreciated!
Last edited: