A perfect matching of a simple graph $G$ is a subset $M$ of the set $E$ of edges of $G$ where no two elements of $M$ share a vertex and every vertex of $G$ is incident with an element of $M$. What is an example of a regular simple graph (every vertex has the same degree) of degree $3$ with no perfect matching?


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.