2
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Hint: the central vertex must be paired with one of its three neighbours. By symmetry you can assume it is (say) the one directly below. What does the graph look like after you remove these two vertices? $\endgroup$ – Erick Wong Mar 22 '18 at 5:52
  • $\begingroup$ Have you managed, Bui, to find a matching with seven edges? $\endgroup$ – Gerry Myerson Mar 22 '18 at 6:24
  • 1
    $\begingroup$ I've found 7 matches on the graph. $\endgroup$ – BuiZMath Mar 22 '18 at 6:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.