# Determining the number of simple undirected graphs.

A simple undirected graph has no self-loops and no parallel edges.

Determine the number of simple undirected graphs $$G = (V, E)$$ with $$V = {1, . . . , n}$$

Also, how can I find the number of simple graphs with vertices of degree 1?

Assuming you got $$N$$ vertices and $$M$$ edges, then since you got $$N$$ total vertices, which means that you got $$\sum_{k=1}^{N-1} k = \frac{N(N-1)}{2} = P$$ possible edges. Now out of those $$P$$, pick the $$M$$ that are present, i.e. $$P \choose M$$ :).
• This doesn't seem to answer the question, which is not, "How many labeled graphs on the vertices $1,2\dots,n$ have $M$ edges," but "How many labeled graphs there are in total." The answer should be $2^P$, with $P$ as above. – saulspatz Nov 26 '19 at 14:25