On essentially 4-edge-connected cubic bricks (Q2290348)

Summary: \textit{L. Lovász} [J. Comb. Theory, Ser. B 43, 187--222 (1987; Zbl 0659.05081)] 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 \(\overline{C_6}\) has three removable doubletons.) \textit{M. H. de Carvalho} et al. [ibid. 85, No. 1, 59--93 (2002; Zbl 1024.05071)] proved a conjecture of Lovász which states that every brick, distinct from \(K_4, \overline{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.