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...