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?

Improve this question
$\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$
    – PickupSticks
    Commented Mar 22, 2021 at 23:18

2 Answers 2

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

Improve this answer
$\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
    Commented 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.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .