some Definition:

For a Graph $G=(V,E)$ (here $V=\{v_{m}|m=1,2,...,n\}, E=\{e_{ij}|i,j=1,2,...,n\}$), we define one monochrome color stands for one disjoint perfect matchings and each monochrome color is represented as an integer number $y$. Thus every monochrome colored edge $e_{ij}$ can be seen as lablled by $yy$, which also means that the number list for vertices is $yy$.

One example: let us assume red means number 0. For a perfect matching of $K_{6}$ in red ($e_{1,2}\ ,\ e_{3,4}\ ,\ e_{5,6}$) , the number list $X_{i}$ for vertices ($v_{1}$,$v_{2}$,$v_{3}$,$v_{4}$,$v_{5}$,$v_{6}$) is $X_{i}$ =($v_{1}$,$v_{2}$,$v_{3}$,$v_{4}$,$v_{5}$,$v_{6}$)=(0,0,0,0,0,0).

See the below figure for more understanding:

other Information:

• The number of perfect matchings of a complete graph $K_{2n}$ is $\#PM=PM(K_{2n})=\frac{(2n)!}{n!2^n}$.

• The edge set of $K_{2n}$ can be divided into ($2n-1$) disjoint perfect matching, which is the max number of disjoint perfect matchings (or $max \ disjoint\ PM(𝐾_{2n})=2n-1$).
• The number of 1-factorizations of a complete graph $K_{2n}$ (we call it as $\#$ways for $K_{2n}$) can been obtained from A000438. (example: $\#$ways for $K_{6}$ is $6$)
• For one certain color setting (or 1-factorizations), all perfect matchings of $K_{2n}$ can be written as term $T_{apm}=T_{d}+T_{r}$, where $T_{d}=\sum_{i=1}^{2n-1}X_{i}$, $T_{r}=\sum_{i=2n}^{PM(K_{2n})}X_{i}$.

Question:

1. Let us take the complete graph $K_{6}$ as an example, we know #$PM(K_{6})=15$, $max \ disjoint\ PM(𝐾_{6})=5$ and $\#ways$ $K_{6}=6$. We list one way of color settings for 5 disjoint perfect matchings as the following figure:

• Let us remove the term $T_{d}=\sum_{i=1}^{5}X_{i}$, which comes from the 5 disjoint perfect macthings. And we define the rest term as $T_{r}=\sum_{i=6}^{15}X_{i}$.

notes: example $T_{r_{1}}=\sum_{i=1}^{3}X_{i}$ is the form of $(0,0,0,0,0,0)+(1,1,1,1,1,1)+(2,2,2,2,2,2)$ and should not equal to adding all elements that gives $(3,3,3,3,3,3)$. Thus we mean $(0,0,0,0,0,0)+(1,1,1,1,1,1)+(2,2,2,2,2,2)$ !=$(3,3,3,3,3,3)$

• There are 6 ways of color setting for the 5 disjoint perfect matchings, thus there will be six $T_{r_{j}}$ ($j=6$).
• And then we do the permutation of number list $L=\{0,1,2,3,4\}$. The monochrome color list {red, blue, green, yellow, gray} encodes in one permutation. The total number is Length[Permutations[L]]=120.
• There will be 120*6=720 $T_{r_{k}}, k=1,...,720$, and we find all $T_{r_{k}}$ is different.

So why all the $T_{r_{k}}, k=720$ are different? Is there any proof or theorem instead to write a program to check all the cases?

• For $K_{8}$, we know #$PM(K_{8})=105$, $max \ disjoint\ PM(𝐾_{8})=7$, $\#ways$ $K_{8}=6240$. Then for one way of 7 monochrome color setting, there will be $T_{d}=\sum_{i=1}^{7}X_{i}$ and $T_{r}=\sum_{i=8}^{105}X_{i}$.

• Again we do the permutation of number list $L=\{0,1,2,3,4,5,6\}$, so there will be Length[Permutations[L]]=5040 possibilities.

• There will be 5040*6240=31449600 cases $T_{r_{k}}, k=1,...,31449600$. Will all $T_{r_{k}}$ also be different?

Thank you very much in advance! If there are something unclear, please let me know. Thank you!