On Essentially 4-Edge-Connected Cubic Bricks - Kothari, Nishad; de Carvalho, Marcelo H.; Lucchesi, Cláudio L.; Little, Charles H. C. (The Electronic Journal of Combinatorics, 2020)
Lovász (1987) proved that every matching covered graph G may be uniquely decomposed into a list of bricks (nonbipartite) and braces (bipartite); we let b(G) denote the number of bricks. An edge e is removable if G-e is also matching covered; furthermore, e is b-invariant if b(G-e)=1, and e is quasi-b-invariant if b(G-e)=2. (Each edge of the Petersen graph is quasi-b-invariant.) A brick G is near-bipartite if it has a pair of edges {e,f} so that G-e-f is matching covered and bipartite; such a pair {e,f} is a removable doubleton. (Each of K_4 and the triangular prism C_6 has three removable doubletons.) Carvalho, Lucchesi and Murty (2002) proved a conjecture of Lovász which states that every brick, distinct from K_4, C_6 and the Petersen graph, has a b-invariant edge. A cubic graph is essentially 4-edge-connected if it is 2-edge-connected and if its only 3-cuts are the trivial ones; it is well-known that each such graph is either a brick or a brace; we provide a graph-theoretical proof of this fact. We prove that if G is any essentially 4-edge-connected cubic brick then its edge-set may be partitioned into three (possibly empty) sets: (i) edges that participate in a removable doubleton, (ii) b-invariant edges, and (iii) quasi-b-invariant edges; our Main Theorem states that if G has two adjacent quasi-b-invariant edges, say e_1 and e_2, then either G is the Petersen graph or the (near-bipartite) Cubeplex graph, or otherwise, each edge of G (distinct from e_1 and e_2) is b-invariant. As a corollary, we deduce that each essentially 4-edge-connected cubic non-near-bipartite brick G, distinct from the Petersen graph, has at least |V(G)| b-invariant edges.