Find a set s for theorem 223 when g is a forest show that

Question

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 C_G-S

2. Every component of G - S is factor-critical

Given such an S, the graph contains a 1-factor ⇔ |S| = |C_G-S|.

Why does this imply Tutte's theorem? The first property of S implies |S| ≤ |C_G-S| and the second condition implies |C_G-S| = q(G - S). Tutte's condition then implies |C_G-S| = q(G - S) ≤ |S|, so |S| = |C_G-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 C_a of G - X containing a, and another in the component C_b 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)

 

 

 

 

separate a from b (see Fig.1). 

Hint: Describe in words what the picture suggests