Prove that the $3$-regular graph, the triple flyswat, does not have a perfect matching but does have a matching with seven edges

1.1k Views Asked by At

I am currently struggling with matchings in graph theory. I was wondering if someone could show me the proof/argument or explanation on how to solve it. Here is a picture of the triple flyswat graph

Here is what I do know: The graph contains bridges. So is that a reason it fails having a perfect matching?

There are an even number of vertices so that condition holds but when sketching the graph I notice the condition that every vertex being m-saturated fails.

I start marking matchings in one of the so called "Flyswatters?" Once I get to next flyswatter I see one vertex that is not saturated.

1

There are 1 best solutions below

0
On

The usual way to prove that this graph has a perfect matching has been outlined in comments: in a perfect matching, removing the edge incident to the central vertex must split the graph into three components, two of which have odd order. So there is no perfect matching.

The snazzy way to prove the same thing is through Tutte's theorem. Removing the central vertex leaves three components of odd order, so there is no perfect matching.