2
$\begingroup$

Akbari, Ghodrati, Hosseinzadeh (2017), On the structure of graphs having a unique k-factor, Aust. J. Combin. (pdf) show:

... we prove that there is no r-regular graph (r≥2) with a unique perfect matching.

It seems natural to explore the stronger case:

Question: Does there exist an r-regular graph (r≥2) with a unique maximum matching?

I.e., the same problem with "perfect" replaced by "maximum", thereby including graphs without perfect matchings.

The answer is clearly "no" for r=2 (such graphs are unions of cycles; we can rotate any cycle to give a distinct maximum matching). For r=3, the answer is "no" for bridgeless cubic graphs, which have a perfect matching (by Petersen's Theorem) and therefore the above result applies. I'm not sure beyond this.

$\endgroup$
5
$\begingroup$

Take a maximum matching $M$ and a vertex $v$ not in $M$. If $v$ has a neighbour $w$ not in $M$, then $M+vw$ is a larger matching. So $v$ has a neighbour $x$ which is in an edge $xy$ of $M$. Now $M-xy+vx$ is another maximum matching.

$\endgroup$
1
  • $\begingroup$ Ah thanks. I guess I should have worked that one out myself. (: $\endgroup$ Dec 31 '19 at 4:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.