Perfect matching on a regular graph

Discrete Mathematics Level pending

In this problem, graphs are simple.

A matching on a graph \(G\) is a subset of \(E(G)\) such that no two edges in the subset share an end. The size of a matching is the number of edges in it.

A perfect matching on a graph \(G\) is a matching whose size is \(\left\lfloor \frac{|V(G)|}{2} \right\rfloor\); that is, a matching that's as big as possible given the number of vertices.

For example, in the following image, the left graph shows a matching of size \(2\). It is not perfect, and in fact it doesn't have a perfect matching. Adding an edge to give the right graph, however, gives a matching of size \(3\) and hence a perfect matching.

A \(k\)-regular graph is a graph where every vertex has degree \(k\).

For \(0 \le k \le 2015\), how many values of \(k\) make this statement true: "all \(k\)-regular graphs have a perfect matching"?


Problem Loading...

Note Loading...

Set Loading...