On essentially 4-edge-connected cubic bricks
arXiv:1803.08713 · doi:10.37236/8594
Abstract
Lovász (1987) proved that every matching covered graph may be uniquely decomposed into a list of bricks (nonbipartite) and braces (bipartite); we let denote the number of bricks. An edge is removable if is also matching covered; furthermore, is -invariant if , and is quasi--invariant if . (Each edge of the Petersen graph is quasi--invariant.) A brick is near-bipartite if it has a pair of edges so that is matching covered and bipartite; such a pair is a removable doubleton. (Each of and the triangular prism has three removable doubletons.) Carvalho, Lucchesi and Murty (2002) proved a conjecture of Lovász which states that every brick, distinct from , and the Petersen graph, has a -invariant edge. A cubic graph is essentially -edge-connected if it is -edge-connected and if its only -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 is any essentially -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) -invariant edges, and (iii) quasi--invariant edges; our Main Theorem states that if has two adjacent quasi--invariant edges, say and , then either is the Petersen graph or the (near-bipartite) Cubeplex graph, or otherwise, each edge of (distinct from and ) is -invariant. As a corollary, we deduce that each essentially -edge-connected cubic non-near-bipartite brick , distinct from the Petersen graph, has at least -invariant edges.
Accepted for publication in Electronic Journal of Combinatorics (December 2019)