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

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.

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.