21
$\begingroup$

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!

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!

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ I am intrigued as to the purpose of your first sentence about letting $G(V,E)$ be a graph, given that you never use $G$ or $V$ or indeed $E$ in the remainder. Perhaps more relevantly, if you delete an edge from $K_4$, does this give you another example? You have the cycle $C_4$ doing all the work, and a diagonal edge not appearing in any perfect matchings. $\endgroup$
    – Gordon Royle
    Commented Apr 12, 2017 at 13:34
  • 2
    $\begingroup$ You can get more examples from graphs with exactly one perfect matching. For example, a path with an even number of edges. See this paper link.springer.com/article/10.1007/s00373-014-1463-8 for more on graphs with unique perfect matchings (UPM-graphs) and also this MO question mathoverflow.net/questions/226583/… $\endgroup$
    – Tony Huynh
    Commented Apr 12, 2017 at 13:38
  • $\begingroup$ @GordonRoyle Thank you, this is an example which fits my question 2. Your comment is certainly interesting for me. Mainly I am interested in graphs with many distinct perfect matchings, in particular question 3. But i suspect m=3 is the limit. I should specify that, thank you! $\endgroup$
    – Mario Krenn
    Commented Apr 12, 2017 at 13:59
  • 5
    $\begingroup$ Do you mean disjoint perfect matchings rather than distinct? $\endgroup$
    – Yuzhou Gu
    Commented Apr 12, 2017 at 14:01
  • 1
    $\begingroup$ @Nico Two objects are disjoint if they have empty intersection; they are distinct if they are different. $\endgroup$
    – David Richerby
    Commented Apr 12, 2017 at 22:21

2 Answers 2

Reset to default
22
+50
$\begingroup$

$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$.

Improve this answer
$\endgroup$
9
  • 1
    $\begingroup$ Thank you very much for your answer. Unfortunatly I can not follow some parts of the argument, and I would be grateful for a few more details: 1) "Two perfect matchings form a disjoint union of cycles." - Let's take the example here. There are two disjoint cycles (ad-da; be-ec-cf-fb), right? Then, what do you mean by "swap one of them"? Could you please point this out in my simple example? Thank you very much!! $\endgroup$
    – Mario Krenn
    Commented Apr 13, 2017 at 8:25
  • 2
    $\begingroup$ 1) In your example two matchings share an edge (ad), which is prohibited by your conditions. If there is no common edge, the (necessarily even) cycles have lengths at least 4, and you may replace the edges of one matching belonging to one cycle by the edges of the other one. $\endgroup$
    – Ilya Bogdanov
    Commented Apr 13, 2017 at 8:29
  • 1
    $\begingroup$ Ah I understand, you start with my conditions, sorry. In this example I have (in red) three disjoint perfect matchings (A,B,C), and they lead to D - they form three H. cycles: AB: ab-bf-fc-ce-ed-da; AC: af-fb-be-ec-cd-da; BC: ab-be-ed-dc-cf-fa. Could you please point to the case where some edges "subtends an arc of odd length" or "subtending minimal such arc". Sorry for these, for you certainly trivial, questions. I am excited by your answer, and looking forward to understand it :-) I am very thankful for your time and help! $\endgroup$
    – Mario Krenn
    Commented Apr 13, 2017 at 9:05
  • 3
    $\begingroup$ After ``untangling'' the picture with the first two matchings, you get a cycle of length 6 (it would be better to draw the correspoding untangled picture!). Each edge of the third matching is a chord in this cycle, so it splits the cycle into two arcs; I assume that each of them is subtended by this chord. The length of the arc is merely the number of edges in it. $\endgroup$
    – Ilya Bogdanov
    Commented Apr 13, 2017 at 9:18
  • 2
    $\begingroup$ @Bogdanov - I want to say thank you again. Your answer has been used in a recent article in Physical Review Letters. I am citing this answere, see Reference [24]. Thanks! $\endgroup$
    – Mario Krenn
    Commented Dec 15, 2017 at 15:48
12
$\begingroup$

It looks like Ilya Bogdanov has answered your question, but here is a pointer to related literature.

An edge that appears in at most one perfect matching is known as a forcing edge. Che and Chen have written a survey of the literature on forcing edges and related topics.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .