Counting graphs with even degrees How many non-isomorphic distinct labeled 5-vertex graphs with even degrees are there? The answer is $2^6$, but I don't seem to be able to solve the problem. 
P.S. It's not a homework. I'm just studying for an exam.
 A: We are looking, essentially, for the cycle space of $K_5$, the set of all graphs formed from disjoint unions of cycles.  This fact follows by strong induction on the number of edges: since all degrees are even, the components of the graph cannot be trees, so it must contain a cycle if it is nonempty.
The cycle space is the orthogonal complement of the cut space in the edge space (which is a vector space over $\mathbb F_2$).  The order of the edge space is easy enough to calculate, and it corresponds to all possible graphs with $5$ vertices (not up to isomorphism).  It has order $2^{10}$ since for any graph $G$, each of $10$ edges of $K_5$ can be in $E(G)$ or not in $E(G)$.
The cut space contains the empty graph, $5$ copies of $K_{1,4}$ and $10$ copies of $K_{2,3}$, so it has $16$ graphs in total.  Since it is a subspace of $\mathcal E(G)$, it has a basis of order $4$.  So the cycle space has $2^{10} / 2^4 = 2^6$ members.
A: There's a bijection between the labelled graphs on $n-1$ vertices and the labelled graphs on $n$ vertices with all even degrees (as I described here).  Since there are $2^{\binom{n-1}{2}}$ labelled graphs with $n-1$ vertices, when $n=5$, there are $2^{\binom{4}{2}}=2^6$ labelled graphs with all even degrees.
A: What do you mean by a non-isomorphic labelled graph?
In terms of just 5-vertex graphs, there is one up to isomorphism with no edges, 1 with 3 edges, 1 with 4 edges,  1 with 5 edges, 1 with 6 edges, 1 with 7 edges, 1 with 10 edges.  A total of 7
Edit:  Sorry forgot the 5-cycle :)
