I have the problem of determining how many graphs from the set $\{1, 2, 3, 4, 5\}$ there are, given the property that every vertex is incident to at least one edge. The at least one part of the question is what makes me unsure.
I know how to do a similar problem for a specific amount of edges, and have taken the same approach. Using a table where a $1$ represents an edge between vertexes would look like this:
1 2 3 4 5
1 X 0 0 0 0
2 0 X 0 0 0
3 0 0 X 0 0
4 0 0 0 X 0
5 0 0 0 0 X
Given that points such as $(1, 2)$ and $(2, 1)$ will always mirror each other on this table we only need to count half the values (the $0$ values about the $X$ line for example).
This gives us
$$\frac{4 \cdot 5}{2}$$
spots to represent edges to choose from, so each possible value will be of the form $C(10, n)$.
Finally, I count each possible number of choices to at least one value for each.
Total number of graphs $= C(10,10) + C(10, 9) + C(10, 8) + C(10, 7) + C(10, 6) + C(10, 5)$
I am not sure this works, I think it might count possibilities with less than one edge. Is my logic correct?
Best Answer
For $n>0$, the total number of graphs on $n$ vertices is $2^{n(n-1)/2}$. Let $S_k$ be the set of graphs in which vertex $k$ has no incident edge. Then by inclusion/exclusion, the number of graphs you want is $$|\overline S_1\cap\cdots\cap \overline S_n| =2^{n(n-1)/2}-|S_1\cup\cdots\cup S_n| =(-1)^n+\sum_{k=1}^n(-1)^{n-k}\binom nk2^{k(k-1)/2}$$ which for $n=5$ works out to $768$.
In fact the sequence is A006129.