Factorization of a complete graph on $6$ vertices.

246 Views Asked by At

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.

1

There are 1 best solutions below

2
On

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