The number of labelled graphs with all vertices of even degree

Solution 1:

For the first question, the hint should be $2^{\binom{n-1}{2}}$; it counts the number of labelled graphs on $n-1$ vertices.

There's a bijection between the $2^{\binom{n-1}{2}}$ labelled graphs $G$ on $n-1$ vertices on the vertex set $\{1,2,\ldots,n-1\}$ and labelled graphs on $n$ vertices with even degree $\{1,2,\ldots,n\}$, namely add in the vertex $n$ and connect it to the odd-degree vertices in $G$. There cannot be an odd number of odd-degree vertices in $G$, as this would violate the Handshaking Lemma, so the new vertex will also have even degree.

I don't know what a cut space is either; what does it say in your books/notes? (I'd guess though, that the $2^{n-1}$ is coming from the number of subsets of vertices that have even cardinality.)