Let $G(V,E)$ be a graph. I am searching for graphs with only disjoint perfect matchings (i.e. every edge only appears in at most one of the perfect matchings).
Examples:
- Cyclic graph $C_n$ with even $n$, with $m=2$ disjoint perfect matchings.
- Complete graph $K_4$, with $m=3$ disjoint perfect matchings.
I have three questions:
- How are such graphs called?
- Are there other examples than $C_n$ and $K_4$?
- What is the maximum number $m$ of perfect matchings, if the graph has only completly disjoint perfect matchings?
For question 3, it seems to me that $K_4$ with $m=3$ different, disjoint perfect matchings is the optimum, but I have no proof for that.
Every hint to an answer or to relevant literature would be very much appreciated!
Edit: I am interested in undirected graphs only for the moment.
Edit2: The answer to this question I have used in a recent article in Physical Review Letters, where I cite this MO question as reference [24]. See Figure 2 for a detailed variant of the application of Ilya's answer. Thanks Ilya!
Best Answer
$m=3$ is indeed the maximum, and $K_4$ is the only example for this value of $m$.
Two perfect matchings form a disjoint union of cycles. If there is more than one cycle, then you may swap one of them, obtaining a third matching on the same edges. So any two of the $m$ matchings form a Hamiltonian cycle.
Assume that $m\geq3$; consider a Hamiltonian cycle $v_1,\dots,v_{2n}$ formed by the first two matchings, and check how the third one looks like.
If some its edge $(v_i,v_j)$ subtends an arc of odd length (i.e. if $i-j$ is odd), then we may split the vertices outside this arc into pairs, and split the cycle $v_i,\dots,v_j$ into edges including $(v_i,v_j)$, obtaining a matching intersecting the third one but not coinciding with it. This should not be possible; thus each subtended arc is even.
Now take an edge $(v_i,v_j)$ subtending minimal such arc, and consider an edge $(v_{i+1},v_k)$ of the third matching (going otside this arc). Now split the cycle $v_i,v_j,v_{j+1},\dots,v_k,v_{i+1}$ into edges containing $(v_i,v_j)$, and split all the remaining vertices into edges of the Hamiltonian cycle (it is possible, according to the parity). If $2n>4$, you again get a fourth matching sharing edges with the third ones bot diferent from it.
Thus $2n\leq 4$ and $m\leq 3$.