Is it true, that in every $2$-regular graph with $14$ vertices there is a perfect matching ? If you think it's true - prove it, otherwise show counter-example

This is my exercise. I think that it's true because it doesn't matter how do you draw this graph, it always will be a cycle, and because the cycle has even number of vertices there always will be a perfect matching.

  • $\begingroup$ You might have left out an assumption of connectedness. $\endgroup$ – hardmath Oct 9 '15 at 22:29

HINT: Try making it a pair of $7$-cycles.

  • $\begingroup$ oh my god. I am so embarrassed. Thank you. $\endgroup$ – Filip Kowalski Oct 9 '15 at 21:19
  • $\begingroup$ @You’re welcome. (I think that we’ve all had that feeling a time or two.) $\endgroup$ – Brian M. Scott Oct 9 '15 at 21:22

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.