Characterizations of Bricks and Braces

Recall that a matching covered graph which is free of nontrivial tight cuts is a brace if it is bipartite, and is a brick if it is nonbipartite. In Chapter 4 we presented a proof of Lovász’s Uniqueness Theorem (4.17) for tight cut decompositions, which is one of the cornerstones of this theory. According to that theorem, every matching covered graph has a unique decomposition into bricks and braces (up to multiple edges). The proof of this fundamental result simply relied on the fact that bricks and braces are free of nontrivial tight cuts. But this fact by itself is inadequate to suggest efficient procedures for recognizing these basic objects. In this chapter, we address these issues by establishing characterizations of bricks and braces which lead to polynomial-time recognition algorithms.We deal with bricks in this section and braces in Section 5.4.