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?
A trivalent simple graph without a perfect matching
graph theorymatching-theory
Best Answer
The graph below is an example of such a graph with no perfect matchings.
In fact, it is the smallest such graph. This is due to a theorem of Petersen, which states there is always a matching in 3-regular graphs with at most 2 bridges.