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.

Theorem by Kano, Lee, and Suzuki:

Every connected cubic bipartite simple graph has a $\{C_n:n\ge 6\}$-factor.

If I have a graph, say $G$, that has $6k$ vertices and satisfies the assumption of the theorem, can I just say that $G$ has $C_6$-factor?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

I think this paper is the same as the one at this link which defines the concept as having an $S$-factor if there is a spanning subgraph whose components come from the set $S$. Thus the theorem states that every graph has there is a spanning subgraph which contains only cycles of length 6 or more, not necessarily exactly 6.

If you look at reference [4] in the paper you can see their figure 1 which is a graph with 48 vertices which can be seen to not be able to be decomposed into 8 copies of $C_6$. With some more practise you will be able to manipulate cubic graphs like this and the one in your question yesterday, but it takes some experimentation...

share|improve this answer
    
Does it mean that i cannot use the theorem to say that the graph has $C_6$-factor? –  kim_kibun Feb 20 '13 at 8:58

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.