Existence of Adjacent Cubic Vertices in Minimal Bricks

ABSTRACT A 3‐connected graph is a brick if the remaining graph after deleting any two distinct vertices has a perfect matching; and it is minimal if the removal of any edge of results in a non‐brick graph. Lovász conjectured that every minimal brick contains two adjacent cubic vertices. We show that every minimal brick contains two cubic vertices such that the distance between them is at most 2, and verify the conjecture for minimal bricks with average degree at least 4.5, which in turn implies the existence of two adjacent vertices of degree at most 5.