0
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ It's not clear to me... Can you speak more elaborately? $\endgroup$ – Saptarshi Saha Dec 7 '17 at 9:41
  • $\begingroup$ My goal was to give a hint, not to do your homework for you. What exactly are you confused by? $\endgroup$ – Misha Lavrov Dec 7 '17 at 17:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.