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!

Let $G=(V,E)$ be a complete graph $K_{2n}$ and it has $m$ 1-factors $f_{i,(i=1,\dots,m)}$, where $m=\frac{(2n)!}{n!2^n}$.

Some definition:

• $F=\{f_{1},f_{2},...,f_{2n-1}\}$ is one 1-factorization in $K_{2n}$.
• $S(F)$ is the number of 1-factors in one $F$; and $S(F)=2n-1$.
• $N(F)$ is the number of distinct 1-factorizations in $K_{2n}$;
• If $N(F)=k$, we use $F_{1}$,$F_{2}$,...,$F_{k}$ to indicate distinct $F$ .
• For $K_{2n}$, when $n=1,2,3,4$, we know $N(F)=1,1,6,6240$; see A000438.

For each $f_{i}$ in $K_{2n}$, we label the edges of $f_{i}$ with numbers 1,2,...,(2n-1). For each $f_{i}$ in $F$, none of them are labeled with the same number (which means disjoint 1-factors).

Now we associate with vertex $v$ in $K_{2n}$ with a word (not number) $r$ such that $r$ is the label of the edge incident with $v$ in $f_{i}$ of $K_{2n}$. It's straightforward to check that the resulting code {$r,v\in V$} has desired parameter from $1,2,...,(2n-1)$. We label the coded word in one $f_{i}$ as $W(f_{i})=r_{1}r_{2}...r_{2n}$ (corresponding to the sequence arrangement as $v_{1}v_{2}...v_{2n}$).

see the following two examples for description:

$f_{x}=\{(v_{1}v_{4}),(v_{2}v_{6}),(v_{3}v_{5})\}=\{(11),(22),(33)\}$ : $W(f_{x})=r_{1}r_{2}...r_{6}=123132$ $f_{x}=\{(v_{1}v_{6}),(v_{2}v_{5}),(v_{3}v_{4})\}=\{(22),(44),(55)\}$ : $W(f_{x})=r_{1}r_{2}...r_{6}=245542$

We separate $m$ 1-factors $f_{i}$ into two groups:

• group1: {$f_{i|i=1,2,...,2n-1}$} which forms $F$ (disjoint 1-factors in $K_{2n}$)
• group2: {$f_{i|i=2n,2n+1,...,m}$} which forms $F'$ (remaining 1-factors in $K_{2n}$)

They form two polynomials: $Y(F)=\sum_{i=1}^{(2n-1)} W(f_{i})$ and $Y(F')=\sum_{i=2n}^m W(f_{i})$. Thus there will be $N(F)$ cases for $Y(F')$, which we can use $Y(F')_{1}$, $Y(F')_{2}$, ..., $Y(F')_{N(F)}$to indicate.

Question:

For 1-factorization $F$, one can permute the numbers from ($1,2,...,2n-1$) to label each $f_{i}$ in $F$, thus there will be $(2n-1)!$ label settings. In addition, there are in total $N(F)$ 1-factorizations in $K_{2n}$. Therefore we know there will be $t=N(F)*(2n-1)!$ cases for $Y(F')$.

$\exists i,j\in [1,t]$ and $i\not\equiv j$, $Y(F')_{i}==Y(F')_{j}$?