# Factorization of a complete graph on $6$ vertices.

Two edges of a graph are called disjoint if they don't share a common vertex. Let $G$ be a complete graph on 6 vertices. So, It has $15$ edges. A triple is defined to be a subset ${a,b,c\$} of pairwise disjoint edges. A factorization of G is a partition of its edges into 5 disjoint triples.

Show that any pair $\{a,b,c\}$,$\{d,e,f\}$ of disjoint triples can be uniqely extended to a factorization of G.

Show that there are exactly 6 factorizations of G.

• Given any pair of disjoint triple, I can extend it to a factorization. But I couldn't write it for a general case. – Saptarshi Saha Nov 30 '17 at 9:25

Hint: to avoid drowning in casework, you should begin by showing that the union of two disjoint triples can only be a cycle through all $6$ vertices.
So all we need to do is show that if we've "factored out" the edges in a cycle, the remaining edges can be uniquely partitioned into $3$ more disjoint triples. There's only one case to consider.
The second part can then be done by counting the cycles through all $6$ vertices, which can all be completed to a unique factorization - but every factorization is obtained $\binom 52$ times (for the number of ways to choose $2$ of its triples to make the $6$-vertex cycle).