Calculate number of graphs Hi I have a problem with following assigment. 
We have a simple graph with $6$ vertices and $5$ edges. I need to calculate the number of graphs in which degree of every vertex is bigger than zero.
So my idea is :
$$$$
1) I can choose one starting vertex (6 ways to do so). Number of avalible vertices to connect it, is 5.$$$$
2) I have 2 connected vertices and 4 unconnected. Now there are 4 ways to pick another vertex that hasn't been connected yet and 5 avalible vertices.
$$...$$
And I do it until I have all my vertices taken care off. So number of graphs is :$6\cdot 5 \cdot 4 \cdot 5 \cdot 3 \cdot 5 \cdot 2 \cdot 5\cdot 1\cdot 5$
 A: There aren't any such graphs with three or more components, but there are three such graphs with two components. I'm sure you can find those yourself, so let’s move on to the interesting problem of one component.
Since the graph is one component, and has 6 vertices and 5 edges, it must be a tree. All that remains is to find the number of trees of size 6. There is no known closed formula for the number of trees with $n$ vertices, but there are algorithms to generate them all. If you take a look at sequence A000055 on oeis, you’ll find that for $n=6$ the answer is 6.
Therefore the amount of graphs with 6 vertices and 5 edges with the minimum degree being 1 is $6 + 3 = 9$.
A: The answer of Alice Ryhl concerns the number of isomorphism classes of these graphs. Let's consider the number of such graphs with labeled vertices.
There are $\binom{6}{2} = 15$ possible edges in a graph with 6 vertices, so there are $\binom{15}{5} = 3003$ possible sets of five edges.
Now we need to subtract the graphs with any vertices of degree 0.
If some vertex $v$ is of degree 0, then the five edges are all among the other five vertices. There are $\binom{5}{2} = 10$ edges among those five vertices, so there are $\binom{10}{5} = 252$ graphs with five edges, none incident to $v$.
So we remove $6 \cdot 252 = 1512$.
However, now we have removed any graphs with two isolated vertices, say $v$ and $w$, twice. There are $\binom{4}{2} = 6$ edges among the other four vertices, so there are $\binom{6}{5} = 6$ such graphs for each pair of vertices; we have to add back $15 \cdot 6 = 90$ graphs for this.
So, all in all we have
$$
3003 - 1512 + 90 = 1581
$$
such graphs.
