# $4$-regular graph with exactly one perfect matching

Can there be a $4$-regular graph with exactly one perfect matching? That is a graph that does have a perfect matching, but not two (not necessarily disjoint) perfect matchings.

• If a 4-regular graph has exactly one perfect matching, then removing the edges of that matching should leave a 3-regular with no perfect matching. Probably you can carefully add edges to this graph in such a way that you create exactly one perfect matching. Commented Jan 21, 2016 at 1:36
• I've all but convinced myself that you cannot obtain the desired graph by adding edges to the 3-regular graph I linked to. You're always forced to put an edge between vertex "clusters", and that seems to break the example. Commented Jan 21, 2016 at 23:41
• @AustinMohr I have reached the same conclusion. I suspect the answer to my question is negative. I just cannot compose a proof for my conjecture. Commented Jan 22, 2016 at 10:13

Based on a well-know result due to Kotzig, a graph with a unique perfect matching has a cut edge (see for example the book: Matching Theory by Lovasz and Plummer). But a 4-regular graph cannot have a cut edge, so it cannot have a unique perfect matching.

• I'd like to second this answer. The argument is correct. The "a 4-regular graph cannot have a cut edge" holds more generally: 'any connected regular graph does not have a cut edge'. This follows easily by summing degrees. Commented Mar 17, 2018 at 10:10
• @Peter Even-regular graphs cannot have cut edges, but odd-regulars can. Commented Aug 10, 2020 at 12:40

EDIT 2020-04-13: this suggestion of how to give an easier proof is wrong. I am sorry. I will leave it up as it might be interesting nonetheless. I'll strike the wrong statement. (Of course, obviously, 3-regular graphs can contain a bridge. My apologies.)

Ghodrati has already given a correct proof. It is worth pointing out

it is also possible to deduce this from Petersen's classic theorem on that every bridgeless cubic graph has a perfect matching.

(Arguably, this is a more lightweight tool that Kotzig's theorem used by Ghodrati; that's the main reason why I make this remark).

To see this, simply note that if there were a $$4$$-regular graph with a unique perfect matching, then removing this matching would leave a $$3$$-regular graph without a perfect matching; by Petersen's theorem, it would have to have a bridge; but a $$3$$-regular graph obviously cannot have any bridge, as is easily seen by summing degrees. This proves that a $$4$$-regular graph with a unique perfect matching is impossible.

• But $3$-regular graphs can have bridges too, right? I think this one is a classic example. Commented Mar 17, 2018 at 23:29
• Yep, this answer is incorrect. Commented Nov 23, 2019 at 19:47
• Yes, 3-regular graphs can have bridges, obviously. (Just take any two 3-regular graphs, subdivide an arbitrary edge in each, and connect the tho subdivision-vertices by one new edge: the bridge.) My suggestion was wrong at the (suspicious-because-of-the-word "easily seen") position "cannot have any bridge, as is easily seen by summing degrees". I am sorry, I forgot what I was thinking when I wrote this two years ago. I will edit this 'answer'. Commented Apr 13, 2020 at 14:27