# 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.

-
Just speculation, because I can't prove it at the moment. The edge space of $K_5$ has $2^{10}$ members, since it is a vector space over $\mathbb F_2$ with a basis of order $10$. The cut space will have $1+5+10=16$ members ($5 C 0 + 5 C 1 + 5 C 2$). The cycle space, which is what you want, is the orthogonal complement of the cut space and has $\frac{2^{10}}{2^4} = 2^6$ members. And you distinguish between isomorphic graphs. You're not looking for graphs up to isomorphism. – Andrew Salmon Feb 4 '13 at 7:59
@AndrewSalmon Yes, you're right. The original question was in Persian and I mistranslated "distinct" to "non-isomorphic". Thanks. – Nima Mohammadi Feb 4 '13 at 8:48

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.

-
This generalizes to any number of vertices, right ? – Ewan Delanoy Feb 4 '13 at 8:38
Yes. It does. In general, the basis of the cycle space has order $|E|-|V|+1$. Source: cs.du.edu/~ramki/downloads/papers/circulationsPreprint.pdf Proposition 3 – Andrew Salmon Feb 4 '13 at 8:44

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.

-

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 :)

-
I downvoted this because : 1) You’re mistaking “all degrees even” for “even number of edges” 2) Your statements are grossly false – Ewan Delanoy Feb 4 '13 at 8:01
Sorry I don't see how what I said is false, I merely forgot to include the 5 cycle. – muzzlator Feb 4 '13 at 8:12
The question asked for graphs different up to isomorphism. I see now he actually didn't want it up to isomorphism at all but rather different graphs on the same set of labels. – muzzlator Feb 4 '13 at 8:24