# 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.
{"ft_lang_label":"__label__en","ft_lang_prob":0.9107658,"math_prob":0.9988558,"size":757,"snap":"2021-31-2021-39","text_gpt3_token_len":193,"char_repetition_ratio":0.13014609,"word_repetition_ratio":0.033898305,"special_character_ratio":0.24306473,"punctuation_ratio":0.16774194,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9993723,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-09-27T18:27:12Z\",\"WARC-Record-ID\":\"<urn:uuid:d2bf08da-41b7-47c6-ac68-1c9ae3efaa5c>\",\"Content-Length\":\"133349\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:f9e81349-aec2-4c21-842a-aa0a11efa5d8>\",\"WARC-Concurrent-To\":\"<urn:uuid:7f455901-162a-4c22-aac7-68f3d14029ab>\",\"WARC-IP-Address\":\"151.101.193.69\",\"WARC-Target-URI\":\"https://mathoverflow.net/questions/349421/does-there-exist-an-r-regular-graph-r%E2%89%A52-with-a-unique-maximum-matching\",\"WARC-Payload-Digest\":\"sha1:AZZAGYJ22VJ6BIBNJKHJTGQWEDYBWSNB\",\"WARC-Block-Digest\":\"sha1:TBVEMYCSHVWZQYYNBGO5UEERYBTXDZCK\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-39/CC-MAIN-2021-39_segments_1631780058467.95_warc_CC-MAIN-20210927181724-20210927211724-00709.warc.gz\"}"}