MHB A Subset of a Graph with No Perfect Matching

[joypav]

The problem given is...

Let G be a graph with no perfect matching. Then, for some $S \subset G$,

1. $|S|<O(G−S)$
2. Each vertex in S is adjacent to vertices in at least three odd components of $G−S$.
(where $O(G−S)$ is the number of odd components of $G−S$)

Number 1. is the contrapositive of Tutte's 1-Factor Theorem. So no problems there.

Should number 2. also be proved using the contrapositive? Meaning to show...

$\forall S \subset G$ there exists at least one vertex that is adjacent to less than three odd components of $G-S \implies G$ has a perfect matching

I've tried drawing some sketches for the forward proof... with the subset $S$ and odd and even components, but without much progress. I thought maybe the contrapositive was the way to go, and that I needed to construct a perfect matching. Any help or hints would be greatly appreciated!

 

[joypav]

I think I may have a proof.. I will post it here so the question is complete, but also feel free to make sure it is correct!

Proof:

Case i: $S = \emptyset$
Then both 1. and 2. are obviously true.

Case ii: $S \ne \emptyset$
Assuming 1. to be true, choose the smallest possible $S$ satisfying 1..
Claim: $|G-S|$ is even
Suppose not. Then $\emptyset$ satisfies 1., contradicting that $S$ is the smallest set satisfying 1..
Thus, $|G-S|$ is even.

Choose an arbitrary $v \in V(S)$.
Let $x = $ the number of odd components that $v$ is adjacent to. (we want to show $x \geq 3$)

Let $S^* = S - \left\{v\right\}$.
Then consider the set $G - S^*$.

Note that any components that $v$ was adjacent to when considering the set $G - S$ are merged together when considering $G - S^*$ (meaning, any components that are adjacent to $v$ become one component in our new graph). This new component may be odd or even.

Then,
$O(G - S^*) = O(G - S) - x + \delta$
where $\delta = 0$ if $x$ is even and $1$ if $x$ is odd.

Note the following...
(i.) $|S| + 2 \leq O(G - S)$ (because $|S|$ even $\implies O(G - S)$ even and $|S|$ odd $\implies O(G - S)$ odd)
(ii.) $|S^*| \geq O(G - S^*)$ (otherwise $S^*$ would be a smaller set satisfying 1., contradicting the assumption)Then,

$O(G - S) - x + \delta = O(G - S^*) \leq |S^*| = |S| - 1 \leq O(G - S) - 2 - 1 = O(G - S) - 3$
$\implies O(G - S) - x + \delta \leq O(G - S) - 3$
$\implies x \geq 3 + \delta$
where $\delta$ is $0$ or $1$, completing the proof.