# 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?

Does someone knows a traditional method to solve this? Please help.

• It appears that the question is talking about labeled graphs. That is, we don't consider isomorphic graphs as the same, unless they are identical. So, the question is, how many ways can we choose which edges are in the graph? As to the second part, if all vertices are of degree one, how many edges has the graph? Nov 26, 2019 at 13:14
• Is it labelled graphs you need? If so, it's a duplicate of math.stackexchange.com/questions/3289921/… otherwise a duplicate of math.stackexchange.com/questions/100560/… Nov 26, 2019 at 13:27
• @gilleain No, I don't need labelled graphs. Nov 26, 2019 at 13:28

## 1 Answer

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$$ :).

• Beautiful explaination. Also, to find the number of graphs with all vertices of degree 1, what conditions should I use? Nov 26, 2019 at 13:29
• the ones you mentioned in your question @Ricky Nov 26, 2019 at 13:30
• it's better to ask another question @Ricky Nov 26, 2019 at 13:35
• 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. Nov 26, 2019 at 14:25