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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Ah thanks. I guess I should have worked that one out myself. (: $\endgroup$
    – Rebecca J. Stones
    Dec 31, 2019 at 4:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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