Cycle decompositions V: Complete graphs into cycles of arbitrary lengths

摘要

We show that the complete graph on n vertices can be decomposed into t cycles of specified lengths m_1,..., m_t if and only if n is odd, 3 ≤ mi ≤ n for i = 1,..., t, and m_1 +... + m_t = (~n_2). We also show that the complete graph on n vertices can be decomposed into a perfect matching and t cycles of specified lengths m_1,..., m_t if and only if n is even, 3 ≤ m_i ≤ n for i = 1,..., t, and m_1 +... + m_t = (~n_2) ? n/2.