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$
  • $\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 '19 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 '19 at 13:27
  • $\begingroup$ @gilleain No, I don't need labelled graphs. $\endgroup$ – Ricky Nov 26 '19 at 13:28
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$
  • $\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 '19 at 13:29
  • $\begingroup$ the ones you mentioned in your question @Ricky $\endgroup$ – Ahmad Bazzi Nov 26 '19 at 13:30
  • $\begingroup$ it's better to ask another question @Ricky $\endgroup$ – Ahmad Bazzi Nov 26 '19 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 '19 at 14:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.