Necessity. If $G$ has a perfect matching $M$ and $S \subseteq V$, consider an odd component $C$ of $G - S$. Since $|V(C)|$ is odd, at least one edge of $M$ in $C$ must go to $S$ (the matching restricted to $C$ can match at most $|V(C)|-1$ vertices). These edges are vertex-disjoint in $S$, so $o(G-S) \leq |S|$.

Sufficiency. Assume Tutte's condition $o(G-S) \leq |S|$ for all $S$. Taking $S = \emptyset$: $o(G) = 0$, so $|V|$ is even.

We prove $G$ has a perfect matching by showing the maximum matching $\nu(G) = |V|/2$.

Berge's formula (which we use as a lemma): $\nu(G) = \frac{1}{2}\min_{S \subseteq V}(|V| - o(G-S) + |S|)$. This is equivalent to the Tutte-Berge formula.

If $\nu(G) < |V|/2$, then by Berge's formula, there exists $S$ with $o(G-S) - |S| > 0$, contradicting Tutte's condition.

Direct proof (without Berge's formula). We prove by induction on $|V|$ that Tutte's condition implies a perfect matching exists.

Add edges to $G$ one at a time (maintaining Tutte's condition) until $G$ is maximal with Tutte's condition: no edge can be added without creating a violation. We claim this maximal graph $G^*$ has a simple structure.

In $G^*$: for $S = \emptyset$, the graph is connected (else add an edge between components). For any non-adjacent $u, v$: adding $uv$ must violate Tutte's condition, so there exists $S'$ with $o(G^* + uv - S') > |S'|$, but $o(G^* - S') \leq |S'|$. This forces $u, v \in S'$ and adding $uv$ merges two odd components.

Careful analysis of $G^*$ shows it decomposes into a complete graph on $S$ plus complete graphs on each component of $G^* - S$, where the components are all cliques of odd size connected to all of $S$. In such a graph, a perfect matching is easily constructed: match within odd cliques (leaving one vertex each) and match the remaining vertices to $S$.

The full details use Tutte's condition to verify that $|S| \geq$ number of odd components, ensuring enough vertices in $S$ to absorb the unmatched ones. $\square$