5
$\begingroup$

What is the smallest 3-regular graph to have a unique perfect matching?

With a large enough number of nodes, it is possible for a 3-regular graph to have no perfect matching (example can be seen in this question Cubic graphs without a perfect matching and a vertex incident to three bridges ). So I believe 3-regular graphs with a unique matching likely exists, but I am unsure how to go about constructing and proving what the smallest one is. Likely there is no better answer than to brute force check all the possibilities, so I am hoping someone happens to know what this graph looks like.

Even better: Does anyone know of an online searchable graph database that allows searching for small graphs with certain properties?

$\endgroup$
1
  • $\begingroup$ This has a construction for the densest graph for 2n nodes with a unique perfect matching mathoverflow.net/questions/226583/… Unfortunately this cannot be pared back to a 3-regular graph, as one vertex in this construction is of degree 1, but possibly the construction there could give some related ideas. $\endgroup$ Mar 22, 2021 at 23:18

2 Answers 2

11
$\begingroup$

There is no such graph.

I have some reading to do as my intuition is off, but the details and a related question are available here: 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.

$\endgroup$
1
  • $\begingroup$ The paper of Akbari, Ghodrati, and Hosseinzadeh begins: "Throughout this paper all graphs are finite and simple." Isn't it possible that the "smallest $3$-regular graph with a unique perfect matching" exists and is an infinite graph? $\endgroup$
    – bof
    Mar 23, 2021 at 8:42
4
$\begingroup$

Regarding your second even better question, I warmly suggest the Brendan McKay page on combinatorial objects, that gives many kinds of graph examples.

$\endgroup$
0

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.