1
$\begingroup$

There is something about the proof showing that the number of simple graphs with $n$ vertices is $2^{{n}\choose{2}}$ I don't quite understand.

We know that $2^n$ is the number of subsets of sets with $n$ items. So why shouldn't the number of simple graphs generated from $n$ vertices be $2^n$ instead of $2^{{n}\choose{2}}$.

For example, if I have a three vertices, the number of simple graphs generated is exactly $2^3 = 8$.

What does ${{n}\choose{2}}$ mean exactly in this scenario? Why not ${{n}\choose{3}}$?

$\endgroup$
  • 3
    $\begingroup$ $\binom{n}{r}=\frac{n!}{r!(n-r)!}$ is the binomial coefficient "$n$ choose $r$", the number of ways of selecting $r$ objects from $n$ distinguishable objects. You should know $\binom{n}{2}$ is the number of possible edges in an $n$ element graph. $\endgroup$ – JMoravitz Sep 30 '17 at 2:49
2
$\begingroup$

For a simple labeled graph with $n$ vertices there are $\binom{n}{2}$ pairs of vertices. Edges directly correspond to pairs of vertices. There are $\binom{n}{2}$ possible locations for edges to be then.

Applying multiplication principle to the string of questions "Is this edge in the graph: yes or no (2 options)" we get then a total possible number of collections of edges as $2^{\binom{n}{2}}$. As each graph on $n$ vertices is uniquely described by which edges are present in the graph, we get the result.

$\endgroup$
  • $\begingroup$ Hi, I know that ${n}\choose{k}$ represents the number of ways of ordering $k$ indistinguishable objects in a set of $n$ objects. Then ${n}\choose{2}$ represents the number of ways of ordering $2$ indistinguishable objects in a set of $n$ objects. I am not sure how this definition translate into the number of possible locations for edges. I guess I will need to look up the proof for this $\endgroup$ – Norman Sep 30 '17 at 3:37
  • $\begingroup$ @DetectiveMooch see this related problem. $\endgroup$ – JMoravitz Sep 30 '17 at 3:43
  • $\begingroup$ Thanks. I am a very visual person and I have a very difficult time in seeing why certain combinatorics argument is true. In the first answer, I can clearly visualize edges coming out of a vertex and the idea becomes very intuitive. $\endgroup$ – Norman Sep 30 '17 at 3:46

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.