Lesson 1

We have already seen that perfect matchings in bipartite graphs are described by Hall's condition. Now let us look at arbitrary graphs. At first sight, this should be much harder: odd cycles appear, and Hall's theorem no longer has a left side and a right side.

Surprisingly, there is still a clean condition. For a graph \(G\), let \(o(G)\) denote the number of connected components of \(G\) that contain an odd number of vertices.

The useful way to think about this number is the following. If a graph has a perfect matching, then it cannot have an odd connected component. Indeed, every edge of a matching covers two vertices, and an odd component cannot be split into pairs using only its own vertices. Trivially, this is not enough, for example the graph below has a single component with even number of vertices but no perfect matching exists in it.