Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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 Feb 4 '13 at 8:48
add comment

3 Answers

up vote 1 down vote accepted

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
1  
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
2  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.