A matching of a graph is a subset of its edges no two of which are incident to any single vertex, i.e., each vertex is matched to at most one other vertex by an edge in the matching. Matchings for bipartite graphs are well understood classically, and these classical theorems have been studied extensively in reverse mathematics. The situation for graphs in general is more complicated. Classically, it is known that all graphs have maximal matchings, even when we measure maximality with respect to the set of vertices matched. In this talk, we will consider the complexity of this theorem and its relationship to a particular condition which guarantees an arbitrary graph has a perfect matching (when every vertex is matched). We will see that the situation for locally finite graphs is as elegant as one would expect, but that allowing for infinite degree vertices makes the analysis surprisingly difficult.

This is joint work with Stephen Flood, Matthew Jura, and Tyler Markkanen.