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.

I'm trying to find some hint regarding to this subject as I only found a 14 page paper dated to 1979 by S Quinn on Google.

I'm thinking about the cycle for a vertex and odd/even vertex sets.

Any thoughts or suggestions?

share|improve this question

1 Answer 1

An obvious necessary condition for $K_{m,n}$ to be decomposed into two copies of a graph $G$, is that the number of edges in $K_{m,n}$ is twice the number of edges in $G$. Hence $mn$ must be even. Without loss of generality, assume $m$ is even.

A drawing of a decomposition of $K_{4,5}$ into two isomorphic graphs is given below.

A decomposition of $K_{4,5}$ into two isomorphic graphs.

In general, we can split the vertices in the part of size $m$ into two halves $A$ and $B$, and retain only the edges incident with $A$ in one graph, and retain only the edges incident with $B$ in the other graph.

The result is a decomposition of $K_{m,n}$ into two copies of the graph $K_{m/2,n}$ together with $m/2$ isolated vertices.

share|improve this answer

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.