1-Factorization of complete Graphs

2.3k Views Asked by At

We have a complete graph $K_n$ with $n$ vertices.

Then the number of distinct 1-factorizations of a $K_n$ graph for $K_2$, $K_4$, $K_6$, $K_8$ is 1, 1, 6, 6240 respectively. (see A000438).

I wanted to understand these numbers, but I failed already for the example $K_4$. In my attempts, I would get 3 different 1-factorizations, not one:

1-Factorization of $K_4$

Could you please tell me what I misunderstand?

1

There are 1 best solutions below

2
On BEST ANSWER

A 1-factor is a spanning subgraph, while a 1-factorization of $K_n$ is the partition of $K_n$ into multiple 1-factors.

In the example given in the question, $K_4$ is partitioned into three 1-factors, but there is only one unique way to do that.

As another example, there are 6 ways to 1-factorize $K_6$ into 5 1-factors, as illustrated in the figures below.

1-Factorization of $K_6$