21

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!

Mario Krenn
  • 155
  • 2
    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. – Gordon Royle Apr 12 '17 at 13:34
  • 2
    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 https://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 http://mathoverflow.net/questions/226583/densest-graphs-with-unique-perfect-matching – Tony Huynh Apr 12 '17 at 13:38
  • @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! – Mario Krenn Apr 12 '17 at 13:59
  • 5
    Do you mean disjoint perfect matchings rather than distinct? – Yuzhou Gu Apr 12 '17 at 14:01
  • @TonyHuynh Thank you for your answer, the UPM-graphs are interesting, i haven't thought about that. Are you aware also of examples for many distinct perfect matchings? – Mario Krenn Apr 12 '17 at 14:01
  • @YuzhouGu I am interested in graphs with perfect matchings, where every edge only appears in at most one of the perfect matchings. I don't know whether that's the same as "disjoined" perfect matchings. (That is the reason why I asked "How are such graphs called?") Are those called "disjoined perfect matchings"? Thank you! – Mario Krenn Apr 12 '17 at 14:08
  • 1
    @Nico Two objects are disjoint if they have empty intersection; they are distinct if they are different. – David Richerby Apr 12 '17 at 22:21
  • @DavidRicherby Thank you, that makes perfect sense, I changed the title now accordingly. – Mario Krenn Apr 13 '17 at 07:32

2 Answers2

22

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

Ilya Bogdanov
  • 22,168
  • 1
    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!! – Mario Krenn Apr 13 '17 at 08:25
  • 2
  • 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.
    • – Ilya Bogdanov Apr 13 '17 at 08:29
  • 1
    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! – Mario Krenn Apr 13 '17 at 09:05
  • 3
    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. – Ilya Bogdanov Apr 13 '17 at 09:18
  • 2
    @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! – Mario Krenn Dec 15 '17 at 15:48
  • Rather late to nit-pick, but related questions which link to this one are attracting attention. There is an unstated assumption in this answer that the graph is connected: if that is not so, clearly there can be no Hamiltonian cycle, although equally the same argument can be applied separately to each connected component, and the existence of multiple perfect matchings in one connected component necessarily means that each edge in another connected component is in at least two perfect matchings of the whole graph. – Peter Taylor Jul 05 '21 at 11:10
  • Separately, I think that the final line is misstated. Following the argument of the answer, I think it should say "Thus $2n \le 4$ or $m < 3$." But even then, I can't reconcile $2n \le 4$ with the claim (which I have verified) that $K_4$ is a solution for $m=3$. And, as a final observation, I think you may be assuming that the graph is simple. @MarioKrenn certainly seems to rely on this in referring to this answer, but with $n=2$ a non-simple loopless graph has a disjoint perfect matching per edge, and although any two of them form a Hamiltonian cycle, they don't generate a third. – Peter Taylor Jul 05 '21 at 11:16
  • 1
    @PeterTaylor : Yes, I assume the graph is simple, and this seems to be a common trend nowadays, unless otherwise specified. I do not need connectedness; the second abstract just covers the non-connected case, as there will be more than one cycle. Starting from the next paragraph, I work under an (explicitly stated) assumption that $m\geq3$. This being assumed, I get that $nleq 2,$ since the newly constructed matching has precisely two edges in common with the third matching. Finally, the only graph on $2n\leq 4$ vertices having $\geq 3n$ edges is $K_4$... – Ilya Bogdanov Jul 06 '21 at 15:58
  • Ah! I failed to pick up on the subscripting of the $v$s implying that the graph has $2n$ vertices rather than the more conventional $n$. (My observation about the assumption of a simple graph was addressed at MarioKrenn rather than you, hence the at-name). – Peter Taylor Jul 06 '21 at 17:35