6
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Jan 21, 2016 at 1:36
  • $\begingroup$ 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. $\endgroup$ Commented Jan 21, 2016 at 23:41
  • 1
    $\begingroup$ @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. $\endgroup$
    – Untitled
    Commented Jan 22, 2016 at 10:13

2 Answers 2

7
+50
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Commented Mar 17, 2018 at 10:10
  • 1
    $\begingroup$ @Peter Even-regular graphs cannot have cut edges, but odd-regulars can. $\endgroup$
    – domotorp
    Commented Aug 10, 2020 at 12:40
-1
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ But $3$-regular graphs can have bridges too, right? I think this one is a classic example. $\endgroup$
    – Untitled
    Commented Mar 17, 2018 at 23:29
  • 1
    $\begingroup$ Yep, this answer is incorrect. $\endgroup$ Commented Nov 23, 2019 at 19:47
  • $\begingroup$ 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'. $\endgroup$ Commented Apr 13, 2020 at 14:27

You must log in to answer this question.

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