Prove that there are $2^{\binom{n−1}{2}}$ labelled graphs on n vertices where every vertex has even degree I took small values of $n$, and we can prove the statement by enumeration in this case. But for larger values of $n$ this is not tenable. I cannot seem to find a pattern to generalize. Also, I tried to use induction but I can't complete the induction step. Is there a direct way to prove the assertion?
 A: HINT 1: Construct a bijection between the labeled graphs with $n-1$ vertices and the labeled graphs with $n$ vertices and no odd-degree vertex.
HINT 2:

 Use the handshaking lemma to notice that a graph has even number of odd-degree vertices.

A: The hint is in the number
$$
2^{\binom{n-1}{2}}.
$$
This is the number of labelled $(n-1)$-vertex graphs: there are $\binom{n-1}{2}$ pairs of vertices, and for each pair, we choose whether or not to add an edge.
This prompts us to search for a one-to-one correspondence between:

*

*Type 1: graphs on the vertices $\{1,\ldots,n-1\}$ (with no degree restriction), and

*Type 2: graphs on the vertices $\{1,\ldots,n\}$ where every vertex has even degree.

Since there are precisely $2^{\binom{n-1}{2}}$ graphs of Type 1, if we can find a one-to-one correspondence between Type-1 and Type-2 graphs, then we have shown that there are also precisely $2^{\binom{n-1}{2}}$ graphs of Type 2.
Going from Type 2 to Type 1 is easy: we just delete the vertex $n$.  But can we reverse this process, and thereby find a one-to-one correspondence?  This is where the hints in the comments and Giorgos Giapitzakis's answer come in.
