TITLE: Show that the number of simple graphs with $n$ vertices is $2^{{n}\choose{2}}$
QUESTION [2 upvotes]: 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}}$?

REPLY [3 votes]: 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.
{"set_name": "stack_exchange", "score": 2, "question_id": 2451114}