Gallai's Lemma certainly follows from the somewhat more general [Tutte–Berge formula](http://en.wikipedia.org/wiki/Tutte%E2%80%93Berge_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.