Generating simple near‐bipartite bricks

A brick is a 3‐connected graph such that the graph obtained from it by deleting any two distinct vertices has a perfect matching. A brick G is near ‐ bipartite if it has a pair of edges α and β such that G − { α , β } is bipartite and matching covered; examples are K 4 and the triangular prismC 6 ¯ . The significance of near‐bipartite bricks arises from the theory of ear decompositions of matching covered graphs. The object of this paper is to establish a generation procedure which is specific to the class of simple near‐bipartite bricks. In particular, we prove that every simple near‐bipartite brick G has an edge e such that the graph obtained from G − e by contracting each edge that is incident with a vertex of degree two is also a simple near‐bipartite brick, unless G belongs to any of eight well‐defined infinite families. This is a refinement of the brick generation theorem of Norine and Thomas which is applicable to the class of near‐bipartite bricks. Earlier, the first author proved a similar generation theorem for (not necessarily simple) near‐bipartite bricks; we deduce our main result from this theorem. Our proof is based on a strategy of Carvalho, Lucchesi and Murty and uses several of their techniques and results.