For the exercise B and C let let G be a graph with vertices a and b, and let X ⊆ V (G) \ {a, b} be an a - b separator in G.
A. Find a set S for Theorem 2.2.3 when G is a forest.
Hint : Decide where the leaves should go: in factor-critical components or in S?
Theorem 2.2.3: Every graph G = (V, E) contains a vertex set S ⊆ V with the following two properties:
1. S is matchable to CG-S
2. Every component of G - S is factor-critical
Given such an S, the graph contains a 1-factor ⇔ |S| = |CG-S|.
Why does this imply Tutte's theorem? The first property of S implies |S| ≤ |CG-S| and the second condition implies |CG-S| = q(G - S). Tutte's condition then implies |CG-S| = q(G - S) ≤ |S|, so |S| = |CG-S|.
B. Show that X is minimal as an a - b separator if and only if every vertex in X has a neighbor in the component Ca of G - X containing a, and another in the component Cb of G - X containing b.
Hint: Recall the definitions of 'separate' and 'component'.
C. Let X' ⊆ V (G) \ {a, b} be another a - b separator, and define C'a and C'b)
![2465_Ref_DocumentNo_17071113.png](https://secure.tutorsglobe.com/CMSImages/2465_Ref_DocumentNo_17071113.png)
separate a from b (see Fig.1).
Hint: Describe in words what the picture suggests