2
$\begingroup$

Does there exist a 2-factorization of K9 in which no two 2-factors are isomorphic? How would I do this?My thought was to split the graph into disjoint cycles but that was pretty much it. I couldn't think of where to go from there

$\endgroup$

1 Answer 1

2
$\begingroup$

Well, you should begin by thinking what a $2$-factor of $K_9$ can look like. A $2$-regular graph is a disjoint union of cycles, and there are only four ways to break up $9$ vertices into cycles:

  1. A single $C_9$.
  2. $C_4$ and $C_5$.
  3. $C_3$ and $C_6$.
  4. Three $C_3$'s.

A $2$-factorization of $K_9$ must have $4$ factors, because $K_9$ is regular of degree $8$, so each of these must be used once.

The remainder of this problem wouldn't be out of place on Puzzling StackExchange. Here's one way to do it:

enter image description here

The four factors are in different colors: a black $C_9$, a red $C_4$ and $C_5$, a purple $C_3$ and $C_6$, and three blue $C_3$'s.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .