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...



How many edge-disjoint cycles of length 3 are in the complete graph?
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. 


