Matching Theory Lecture-9 Part-I: Subadditivity of b (no. of bricks) across separating cuts & proof скачать в хорошем качестве

Matching Theory Lecture-9 Part-I: Subadditivity of b (no. of bricks) across separating cuts & proof

In today's lecture, we continued proving the following theorem: Theorem 4.20 (CLM 2002): Let C be a separating cut of a matching covered graph G, and let G1 and G2 denote its C-contractions. Then, b(G) is at most b(G1) + b(G2); furthermore, equality holds if and only if C is a tight cut. We proceed by induction on the order, and we soon hit the situation that C is NOT a tight cut, and that G has a nontrivial tight cut D. (In all other cases, we are able to finish the proof using facts we have already proved.) We now consider two cases: either C and D are laminar, or they cross. This part deals with the laminar case; the next part deals with the crossing case.