Return to Revisions

Gallai's Lemma certainly follows from the somewhat more general Tutte–Berge formula, which easily follows from Tutte's theorem. Suppose that $\nu(G-u)=\nu(G)$ for all $u \in V(G)$ and let $U$ be a set which gives equality in the Tutte-Berge formula. Suppose $U$ is non-empty and $x \in U$. Evidently, $(G-x)-(U-x)$ has the same set of odd components as $G-U$. By the Tutte-Berge formula, it follows that $\nu (G-u) < \nu (G)$, which is a contradiction. Therefore, $U=\emptyset$. Since $G$ is connected, by the Tutte-Berge formula, we have that either $G$ has a perfect matching (if $G$ has an even number of vertices) or a matching covering all vertices except one (if $G$ has an odd number of vertices). Since $\nu(G-u)=\nu(G)$ for all $u \in V(G)$, the first possibility is impossible, and so the second possibility holds. Thus, $G-u$ has a perfect matching for all $u \in V(G)$, as required.