(Solved): Proof of Tutte's Theorem. PLEASE ANSWER EACH PART OF THIS THEOREM. I AM POSTING IT 8 TIMES FOR EAC ...

Proof of Tutte's Theorem. PLEASE ANSWER EACH PART OF THIS THEOREM. I AM POSTING IT 8 TIMES FOR EACH PART !!! Tutte's Theorem The goal is to write up a nice proof of Tutte's theorem - that you can understand and reproduce (and builds on our work on West's paper). 1. We'll prove this by induction. Check that Tutte's Theorem is true for "small" graphs and assume that it is true for graphs with less than n vertices. Let G be a graph with n vertices. 2. Prove the "easy" direction: assume G has a perfect matching and show that, for every subset of vertices S, that o(G - S) ?|S|. 3. Now we will prove the "hard" direction. Assume that for every subset of vertices S, that o(GS) ? |S|. Let T be a set that maximizes the deficiency (so def(T) = de f(G)). Argue that o(GT) = |T|. 4. Assume too that T is maximal-no proper superset of T has the same deficiency. Argue that every component of G-T is odd (if there were an even component T would not be maximal. Why?) 5. Let H(T) be the auxiliary bipartite graph defined in class. Use Hall's Theorem to argue that there is a matching that saturates T in H(T). (Why?) 6. Then argue that this matching must saturate Y in H(T) (use that o(G – T) = |T| in G). So H(T) has a perfect matching. 7. So this matching will saturate T and one vertex u; of each component C; of the |T| odd components of G - T. So we only need to show that for each component C; the remaining vertices can be perfectly matched. So consider the subgraph C; - u; a subset SC V(C; - u;), and argue that Ciui - S has no more than |S| components. (How?). Then the induction hypothesis implies that Ciui has a perfect matching. 8. Finish by explaining how the original graph G has a perfect matching.