Skip to main content
1 of 5
Mario Krenn
  • 155
  • 12
  • 35

Graphs with only distinct perfect matchings

Let $G(V,E)$ be a graph. I am searching for graphs with only distinct 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$ distinct perfect matchings.
  • Complete graph $K_4$, with $m=3$ distinct 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 of perfect matchings, if the graph has only completly distict perfect matchings?

For question 3, it seems to me that $K_4$ with 3 different, distinct 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