How to Build a Brick

An edge $e$ of a brick $G$ is {\em removable} if $G-e$ is matching covered. A removable edge $e$ is {\em $b$-invariant} if $G-e$ has exactly one brick. A removable edge $e$ is {\em thin} if, for each barrier $B$ of $G-e$, the graph $G-e-B$ has precisely $|B|-1$ isolated vertices, each of which has degree two in $G-e$. Improving upon a theorem proved in [4] and [5], we show here that every brick different from the three basic bricks $K_4$, $\overline{C}_6$ and the Petersen graph has a $b$-invariant edge that is thin. It follows from this result that all bricks can be generated from the three basic bricks by means of four simple operations. A cut $C$ of a brick $G$ is a {\em separating} cut of $G$ if each of the two graphs obtained by shrinking a shore of $C$ to a single vertex is matching covered. A brick is {\em solid} if it does not have any nontrivial separating cuts. Solid bricks have many interesting properties ([4]) and may be thought of as building blocks of bricks themselves. The complexity status of deciding whether a given brick is solid is not known. Here, by using our theorem on the existence of thin edges, we show that every simple planar solid brick is an odd wheel.

2003