Let $G$ be a graph with a perfect matching, I want to prove that if no Tutte set contains both $x$ and $y$, then there is a perfect matching contains the edge $xy$.
Tutte set is defined as a set of vertices with maximum deficiency. For any set of vertices in $G$, the deficiency is defined as $$def(S)=o(G-S)-|S|$$ where $o(G-S)$ is the number of odd components in $G-S$.
I can show that if $S=\{ x,y\}$, then $G-S$ only contains even components since $S$ is not a Tutte set, my idea is to deduce that a perfect matching can be obtained by pairing vertices in each even components and together with the edge $xy$, we have a perfect matching containing $xy$, but I an not sure how to deduce that.
Best Answer
We need to show that $G - S$ contains a perfect matching; then we can take such a matching and add $xy$ to get a perfect matching of $G$.
Suppose indirectly that there is no perfect matching in $G-S$. Then by Tutte's theorem there is a set $X \subseteq V - S$ such that $o(G-S-X) > |X|$. Since $G$ has a perfect matching, applying Tutte's condition to $S \cup X$ we get $o(G - S - X) \leq |S \cup X| = |X| + 2$, and in fact this inequality is strict, for otherwise $S \cup X$ would be a Tutte set containing $S$. The only possibility then is $o(G-S-X) = |X| + 1$. But this is impossible for parity reasons (do you see why?).