[proofplan] We prove necessity directly from a perfect matching: every odd component of $G-S$ must be matched to a distinct vertex of $S$. For sufficiency, we prove the contrapositive by enlarging $G$ to an edge-maximal graph $H$ with no perfect matching. The maximality forces the components outside the set of universal vertices to be complete; if Tutte's inequality held there, those complete components and the universal vertices could be matched explicitly, contradicting maximality. Finally, deleting the extra edges from $H$ back to $G$ can only refine components, and this preserves enough odd components to transfer the violation to $G$. [/proofplan] [step:Show that a perfect matching forces every odd component of $G-S$ to meet $S$ through the matching] Assume $G$ has a perfect matching $M\subset E$. Fix a subset $S\subset V$. Let $C$ be a connected component of $G-S$ with $|V(C)|$ odd. No edge of $M$ can match all vertices of $C$ internally, because every internal matching edge covers two vertices of $C$ and $|V(C)|$ is odd. Since $M$ covers every vertex of $G$, at least one vertex of $C$ is matched by an edge of $M$ to a vertex outside $C$. Because $C$ is a connected component of the induced subgraph $G-S$, there is no edge of $G$ from $C$ to another component of $G-S$. Hence this matching edge joins a vertex of $C$ to a vertex of $S$. Distinct odd components of $G-S$ require distinct vertices of $S$, since a vertex of $S$ is incident to at most one edge of the matching $M$. Therefore the assignment sending each odd component to the $S$-endpoint of one such matching edge is injective. Thus \begin{align*} o(G-S)\leq |S|. \end{align*} [guided] Assume $G$ has a perfect matching $M\subset E$, meaning every vertex of $V$ is incident to exactly one edge of $M$. We must prove that every subset $S\subset V$ satisfies the inequality \begin{align*} o(G-S)\leq |S|. \end{align*} Fix $S\subset V$, and let $C$ be a connected component of $G-S$ such that $|V(C)|$ is odd. The key parity observation is that the matching cannot cover all vertices of $C$ using only edges whose two endpoints both lie in $C$. Each such edge covers exactly two vertices, so internal matching edges cover an even number of vertices. Since $|V(C)|$ is odd, at least one vertex of $C$ must be matched by an edge of $M$ to a vertex outside $C$. Now we identify where that outside endpoint can lie. The graph $G-S$ is the induced subgraph on $V\setminus S$, and $C$ is a connected component of that graph. Therefore no edge of $G$ joins a vertex of $C$ to a vertex of another component of $G-S$; otherwise the two components would be connected in $G-S$. Hence any edge leaving $C$ must have its other endpoint in $S$. Thus each odd component of $G-S$ contributes at least one matching edge from that component into $S$. Finally, two different odd components cannot use the same vertex of $S$, because $M$ is a matching and each vertex of $S$ is incident to at most one edge of $M$. Therefore the odd components of $G-S$ inject into $S$, and hence \begin{align*} o(G-S)\leq |S|. \end{align*} [/guided] [/step] [step:Pass to an edge-maximal supergraph with no perfect matching] We prove the converse by contrapositive. Suppose $G$ has no perfect matching. If $|V|$ is odd, then with $S=\varnothing$ the graph $G-S=G$ has at least one odd component, because the sum of the component orders is odd. Hence \begin{align*} o(G)>0=|\varnothing|, \end{align*} so Tutte's inequality fails. Assume therefore that $|V|$ is even. Among all simple graphs on the vertex set $V$ that contain $G$ as a spanning subgraph and have no perfect matching, choose one, denoted $H=(V,E_H)$, that is maximal with respect to inclusion of the edge set. This is possible because there are only finitely many simple graphs on $V$. Thus $G\subset H$, the graph $H$ has no perfect matching, and for every non-edge $xy\notin E_H$ with $x\neq y$, the graph $H+xy$ has a perfect matching. For such a non-edge $xy$, every perfect matching of $H+xy$ must contain the added edge $xy$; otherwise it would already be a perfect matching of $H$. Consequently, \begin{align*} H-x-y \end{align*} has a perfect matching, obtained by deleting the edge $xy$ from a perfect matching of $H+xy$. [/step] [step:Prove the maximality lemma for paths of length two] [claim:A middle vertex on an induced two-edge path is universal] Let $a,b,c\in V$ be distinct vertices such that $ab\in E_H$, $bc\in E_H$, and $ac\notin E_H$. Then $b$ is adjacent in $H$ to every vertex of $V\setminus\{b\}$. [/claim] [proof] Suppose, toward a contradiction, that there exists a vertex $x\in V\setminus\{b\}$ with $bx\notin E_H$. Since $ab,bc\in E_H$, the vertex $x$ is distinct from both $a$ and $c$. By maximality applied to the non-edge $ac$, let $M$ be a perfect matching of $H-a-c$. By maximality applied to the non-edge $bx$, let $N$ be a perfect matching of $H-b-x$. Consider the graph $F=(V,M\cup N)$. Every vertex of $V\setminus\{a,b,c,x\}$ has degree $2$ in $F$ if its incident edges in $M$ and $N$ are distinct and degree $1$ if those two edges coincide. The vertices $a$ and $c$ are incident only to their $N$-edges, while $b$ and $x$ are incident only to their $M$-edges. Hence the connected components of $F$ that are not even cycles or doubled matching edges are alternating paths whose endpoints lie in the set $\{a,c,b,x\}$. Let $P$ be the alternating path component of $F$ containing $b$. The other endpoint of $P$ is one of $a,c,x$. If the other endpoint is $a$, then the symmetric difference $M\triangle E(P)$ is a matching that covers every vertex except $b$ and $c$. Adding the edge $bc\in E_H$ gives a perfect matching of $H$, a contradiction. If the other endpoint is $c$, then $M\triangle E(P)$ is a matching that covers every vertex except $a$ and $b$. Adding the edge $ab\in E_H$ gives a perfect matching of $H$, a contradiction. If the other endpoint is $x$, then the remaining two endpoints $a$ and $c$ lie in a second alternating path component $Q$ of $F$. The symmetric difference $M\triangle E(Q)$ is a perfect matching of $H$, because $Q$ starts and ends with edges of $N$ and replaces one fewer $M$-edge by one more $N$-edge, thereby matching precisely the two vertices $a$ and $c$ that were unmatched by $M$. This is again a contradiction. All cases contradict the assumption that $H$ has no perfect matching. Therefore no such vertex $x$ exists, and $b$ is adjacent to every vertex of $V\setminus\{b\}$. [/proof] [guided] We prove the claim in detail because this is the point where edge-maximality is converted into structure. Let $a,b,c\in V$ be distinct vertices with \begin{align*} ab\in E_H,\qquad bc\in E_H,\qquad ac\notin E_H. \end{align*} We want to prove that $b$ is adjacent to every other vertex. Suppose instead that there is a vertex $x\in V\setminus\{b\}$ such that $bx\notin E_H$. Since $b$ is adjacent to both $a$ and $c$, this vertex $x$ cannot equal $a$ or $c$. The maximality of $H$ says that adding any missing edge creates a perfect matching. Apply this first to the missing edge $ac$. The graph $H+ac$ has a perfect matching, and that matching must use the added edge $ac$; otherwise it would already be a perfect matching of $H$. Removing $ac$ leaves a perfect matching $M$ of $H-a-c$. Apply the same reasoning to the missing edge $bx$. The graph $H+bx$ has a perfect matching using $bx$, so deleting $bx$ leaves a perfect matching $N$ of $H-b-x$. Now compare the two matchings $M$ and $N$ inside the graph \begin{align*} F=(V,M\cup N). \end{align*} The matching $M$ covers every vertex except $a$ and $c$, while $N$ covers every vertex except $b$ and $x$. Thus $a$ and $c$ are incident only to $N$-edges in $F$, and $b$ and $x$ are incident only to $M$-edges in $F$. Every other vertex is incident to one edge from $M$ and one edge from $N$, unless the two matchings use the same edge there. Consequently, the non-cycle components of $F$ are alternating paths whose endpoints are among $a,c,b,x$. Let $P$ be the alternating path component containing $b$. Since $b$ is not covered by $N$, the path $P$ starts from $b$ with an edge of $M$. Its other endpoint is one of $a,c,x$. If $P$ ends at $a$, then toggling along $P$ replaces the $M$-edges of $P$ by the $N$-edges of $P$. The resulting matching $M\triangle E(P)$ covers every vertex except $b$ and $c$. Because $bc\in E_H$, adding $bc$ produces a perfect matching of $H$, contradicting the choice of $H$. If $P$ ends at $c$, the same toggling gives a matching covering every vertex except $a$ and $b$. Since $ab\in E_H$, adding $ab$ gives a perfect matching of $H$, again a contradiction. The remaining case is that $P$ ends at $x$. Then the two endpoints not used by $P$ are $a$ and $c$, so they lie in another alternating path component $Q$ of $F$. This path $Q$ starts and ends with edges of $N$, because $a$ and $c$ are unmatched by $M$ but matched by $N$. Toggling $M$ along $Q$ replaces one fewer $M$-edge by one more $N$-edge, and therefore exactly fills the two unmatched vertices $a$ and $c$. Thus $M\triangle E(Q)$ is a perfect matching of $H$, another contradiction. Every possible endpoint pairing gives a perfect matching of $H$, impossible by construction. Hence the assumed non-neighbour $x$ of $b$ cannot exist, and $b$ is adjacent to every vertex of $V\setminus\{b\}$. [/guided] [/step] [step:Show that the components outside the universal vertices are complete] Define \begin{align*} S:=\{v\in V:\text{$v$ is adjacent in $H$ to every vertex of $V\setminus\{v\}$}\}. \end{align*} Thus $S$ is the set of universal vertices of $H$. We claim that every connected component of $H-S$ is complete. Suppose not. Then some connected component $C$ of $H-S$ contains two non-adjacent vertices. Among all paths in $C$ whose endpoints are non-adjacent in $H$, choose one of minimal length, and write it as \begin{align*} v_0,v_1,\dots,v_k \end{align*} with $k\geq 2$, $v_0v_k\notin E_H$, and $v_{i-1}v_i\in E_H$ for $1\leq i\leq k$. Minimality implies $v_0v_2\notin E_H$; if $v_0v_2\in E_H$, then \begin{align*} v_0,v_2,v_3,\dots,v_k \end{align*} would be a shorter path in $C$ with the same non-adjacent endpoints. Since $v_0v_1\in E_H$, $v_1v_2\in E_H$, and $v_0v_2\notin E_H$, the claim from the previous step implies that $v_1$ is universal in $H$. Hence $v_1\in S$, contradicting $v_1\in V(C)\subset V\setminus S$. Therefore every connected component of $H-S$ is complete. [/step] [step:Construct a perfect matching of $H$ if $o(H-S)\leq |S|$] Let $C_1,\dots,C_m$ be the connected components of $H-S$, and let \begin{align*} q:=o(H-S) \end{align*} be the number of those components with odd cardinality. By the previous step, each $C_i$ is a complete graph. Assume, toward a contradiction, that $q\leq |S|$. Choose the odd components and denote them by \begin{align*} C_{i_1},\dots,C_{i_q}. \end{align*} Choose distinct vertices \begin{align*} s_1,\dots,s_q\in S \end{align*} and choose one vertex \begin{align*} c_j\in V(C_{i_j}) \end{align*} for each $1\leq j\leq q$. Since every vertex of $S$ is universal in $H$, each edge $s_jc_j$ lies in $E_H$. For each odd component $C_{i_j}$, the graph induced by $V(C_{i_j})\setminus\{c_j\}$ is complete of even order, so its vertex set can be partitioned into two-element subsets, each of which is an edge. This gives a perfect matching of $C_{i_j}-c_j$. Each even component $C_i$ of $H-S$ is complete of even order, and the same two-element partition argument gives a perfect matching of $C_i$. It remains to match the unused vertices of $S$. The unused set is \begin{align*} S_0:=S\setminus\{s_1,\dots,s_q\}. \end{align*} The vertices of $S$ are pairwise adjacent because each of them is universal, so $H[S_0]$ is complete. Also $|S_0|=|S|-q$ is even: the parity identity \begin{align*} |V|=|S|+\sum_{i=1}^{m}|V(C_i)| \end{align*} and the fact that the number of odd summands among the $|V(C_i)|$ is $q$ give \begin{align*} |V|\equiv |S|+q \pmod 2. \end{align*} Since $|V|$ is even, $|S|-q$ is even. Hence $H[S_0]$ has a perfect matching. Combining the edges $s_jc_j$, the perfect matchings inside the modified odd components, the perfect matchings inside the even components, and the perfect matching of $H[S_0]$ gives a perfect matching of $H$. This contradicts the construction of $H$. Therefore \begin{align*} o(H-S)=q>|S|. \end{align*} [/step] [step:Transfer the violated inequality from $H$ back to $G$] We have found a subset $S\subset V$ such that \begin{align*} o(H-S)>|S|. \end{align*} Because $G\subset H$ and both graphs have the same vertex set, the graph $G-S$ is obtained from $H-S$ by deleting edges. Hence every connected component of $G-S$ is contained in a connected component of $H-S$. Let $D$ be a connected component of $H-S$. The connected components of $G-S$ contained in $D$ partition $V(D)$. If $|V(D)|$ is odd, then the number of odd-cardinality parts in this partition is odd, hence at least one. Therefore every odd component of $H-S$ contributes at least one odd component of $G-S$. It follows that \begin{align*} o(G-S)\geq o(H-S)>|S|. \end{align*} Thus $G$ fails Tutte's inequality for the subset $S$. We have proved the contrapositive: if $G$ has no perfect matching, then there exists $S\subset V$ such that $o(G-S)>|S|$. Therefore, if $o(G-S)\leq |S|$ for every $S\subset V$, the graph $G$ has a perfect matching. Together with the necessity proved above, this completes the proof. [/step]