- Thread starter
- #1

**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$)

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!