Para lançar um pouco mais de luz sobre as técnicas usadas na teoria do emparelhamento, damos agora uma segunda prova do teorema de Tutte. De fato, provaremos um resultado um pouco mais forte, um resultado que coloca uma estrutura interessante do ponto de vista de um emparelhamento em um “grafo arbitrário”. Se o grafo satisfizer a condição do teorema de Tutte, essa estrutura produzirá imediatamente um $1$-fator, isto é, um emparelhamento perfeito.

Um grafo não vazio $G$ é chamado de “fator-crítico” se $G$ não tem $1$- fator, mas para cada vértice $v \in G$ o grafo $G-v$ tem um $1$-fator. Chamamos um conjunto de vértices $S \subseteq V$ compatível,ou emparelhável, com $\mathcal{C}_{G-S}$ se o grafo (bipartido) $G_{S}$, que surge de $G$ contraindo os componentes $C \in \mathcal{C}_{G-S}$ para vértices únicos e excluindo todas as arestas dentro de $S$, contém um emparelhamento de $S$ (Formalmente, $G_{S}$ é o grafo com conjunto de vértices $S \cup \mathcal{C}_{G-S}$ e conjunto de arestas $\{sC | \exists c \in C : sc \in E \}$(veja a figura abaixo)).

Para qualquer $G$ dado, a afirmação do teorema de Tutte decorre facilmente deste resultado. De fato, por $(i)$ e $(ii)$ temos $|S| \leq |\mathcal{C}_{G-S}| = q(G-S)$, uma vez que os grafos fator-crítico têm ordem ímpar; assim, a condição de Tutte de $q(G-S) \leq |S|$ implica $|S| = |\mathcal{C}_{G-S}|$, e a existência de um $1$-fator decorre da última declaração do teorema.