MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

A couple of questions related to edge-disjoint cycles.

Let $K_n = (V,E)$ be the complete graph on $|V|=n$ nodes. Two cycles are 'edge disjoint' if they do not share any edges.

  • What is the size of the largest collection of edge-disjoint cycles of length 3 in Kn?

  • Consider a spanning tree sub-graph of $K_n$ (so any spanning tree on $n$ nodes). Is there an efficient algorithm for adding $c$ edges such that each edge creates a cycle of length 3 and is edge-disjoint with all other cycles added?

Any references or ideas would be greatly appreciated!


share|cite|improve this question
If I understand the second question correctly, you want $c\le n/2$? – Gjergji Zaimi Nov 20 '11 at 12:31
The first question does not quite make sense. Do you want the size of the maximal collection of edge-disjoint triangles? – Igor Rivin Nov 20 '11 at 12:33
$n \equiv 1,3 \mod 6$ iff there is a Steiner triple system on $n$ points, which is equivalent to a partition of the edges of $K_n$ into triangles. – Douglas Zare Nov 20 '11 at 13:07
Thanks for the quick replies. Yes, I meant the size of the maximal collection of edge-disjoint triangles. I updated the post accordingly. For the maximum value of c in the second question, that would be upper bounded by the answer to the first question. Thanks for the Steiner triple reference, I will look into that. – dan Nov 20 '11 at 13:21
up vote 11 down vote accepted

The maximum number of edge-disjoint triangles in a complete graph is determined by:

Joel Spencer. Maximal consistent families of triples. J. Combinatorial Theory, 5 1968 1–8.

share|cite|improve this answer

Your Answer


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.