# Show that the number of simple graphs with $n$ vertices is $2^{{n}\choose{2}}$

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}}$?

• $\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. – JMoravitz Sep 30 '17 at 2:49

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.
• 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 – Norman Sep 30 '17 at 3:37