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).
- 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 . See Figure 2 for a detailed variant of the application of Ilya's answer. Thanks Ilya!