Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 1 down vote favorite

Given there are $n$ vertex. How to calculate total number of distinct graph having all $n$ vertex. Is there any formula for that?

Sorry one correction here: There is one more rule that there should not be any circular (not finding the correct word) path.

example: If there is one path $v_1 \to v_2 \to v_3$ There should be no path from $v_1 \to v_3$ in the same graph.

share|improve this question
Did you do any kind of search at all to see if this problem has been addressed? I think if you had - for example, if you had searched Google for anything like "number of distinct graphs with n vertices" you would have found a link to this: oeis.org/A000088. – Steve Kass Feb 3 at 7:27
@SteveKass Sorry I updated the question with more details. I think I have not explained problem correctly. – user1779660 Feb 3 at 7:34
You want to count what are called "acyclic" graphs. If you had the additional condition that the graphs you count are connected, you are counting the number of non-isomorphic "trees" (trees are connected, acyclic graphs) with n vertices. There is a famous result due to Cayley (look up "Cayley's Formula") that gives the answer as $n^{n-2}$. If you are not requiring that the graphs are connected, I don't know if it is a well-known result, but you can use Cayley's formula to help look for an answer. – Steve Kass Feb 3 at 7:42
@SteveKass The $n^{n-2}$ count is only correct for labeled trees. For example, for $n=3$, there is only one unlabeled tree with 3 nodes (a path of length 3), but there are 3 ways you could label the central node, thus giving the count 3 for labeled trees. – Ted Feb 3 at 7:48
@Ted: My bad. Yes, Cayley's formula is for labeled trees, so it doesn't help so much... – Steve Kass Feb 3 at 7:51
show 1 more comment

2 Answers

up vote 1 down vote

Note that there are $\dbinom{n}2$ possible edges. To construct a graph, between two vertices, you have the option to choose an edge or not choose an edge. Can you now work out how many graphs are possible?

EDIT

Answer to the new question. The number of trees on $n$ labelled vertices is $n^{n-2}$. In your case, since you do not enforce that your graph is connected (but there should be no cycle) the answer is $$1+\sum_{k=2}^n \dbinom{n}k k^{k-2}$$ i.e. you choose $k$ vertices and have a tree within these $k$ vertices and letting $k$ run from $2$ to $n$ should give you the answer. You need to add $1$ since a graph with no edges also satisfies you criteria.

share|improve this answer
You will get every non-complete graph multiple times this way. For example, every graph you get by choosing only one of the possible edges will be the same. – Steve Kass Feb 3 at 7:26
@SteveKass I assume all the vertices/nodes are distinguishable. – user17762 Feb 3 at 7:27
Yes, for graphs with labeled vertices, your hint is a good one. (For what it's worth, "graph" is usually defined to have unlabeled vertices, though.) – Steve Kass Feb 3 at 7:29
@Marvis Sorry I updated the question with more details. I think I have not explained problem correctly. – user1779660 Feb 3 at 7:35
Graphs are definitely not usually defined to have "unlabelled vertices". A graph is defined to be a set of vertices and a set edges such that.... The vertices are elements of a set and hence are distinct. – Chris Godsil Feb 3 at 13:13
up vote 0 down vote

Kindly see Probability that an undirected graph has cycles, the answer to your Q is there.

If the graph is labeled, it is the Cayley's formula. Otherwise an exponential solution on the same page.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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