Skip to main content
3 of 5
changed title from distinct -> disjoined, as suggested by Yuzhou Gu
Mario Krenn
  • 155
  • 12
  • 35

Graphs with only disjoint perfect matchings

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:

  1. How are such graphs called?
  2. Are there other examples than $C_n$ and $K_4$?
  3. 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!

Mario Krenn
  • 155
  • 12
  • 35