# How many edge-disjoint cycles of length 3 are in the complete graph?

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!

thanks...

• If I understand the second question correctly, you want $c\le n/2$? Nov 20, 2011 at 12:31
• The first question does not quite make sense. Do you want the size of the maximal collection of edge-disjoint triangles? Nov 20, 2011 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. Nov 20, 2011 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, 2011 at 13:21