2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – saulspatz
    Nov 26, 2019 at 13:14
  • $\begingroup$ 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/… $\endgroup$
    – gilleain
    Nov 26, 2019 at 13:27
  • $\begingroup$ @gilleain No, I don't need labelled graphs. $\endgroup$
    – Ricky
    Nov 26, 2019 at 13:28

1 Answer 1

1
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .