I would like to prove the statement that there are $2^{\binom{n-1}{2}}$ simple graphs are there with vertex set $\{1,\ldots,n\}$ such that every vertex has even degree.
The thing that confuses me is the $\binom{n-1}{2}$: this is the place that I use to start attacking the problem, I guess the $n-1$ means the vertex other than itself, so from a vertex we can have $n-1$ edge joining the vertex to the remaining vertex and the two means choosing two vertices to create an edge.
But somehow if I use this line of reasoning, it seems that we can only have a maximum degree for each vertex is 2.
Can anybody please give me some helpful hints so that I can start thinking in the correct direction?
Many thanks!
Hints: The $\binom{n-1}{2}$ refers to the number of unordered pairs of vertices selected from the first $n-1$ vertices. We have $2$ raised to this power because for each such pair of vertices, we can either choose for them to be connected by an edge or not. The $n^{\text{th}}$ vertex is used to make sure that every vertex has even degree.
Can you use this information to account for every such graph?