Wheel‐Like Bricks and Minimal Matching Covered Graphs

ABSTRACT A connected graph with at least two vertices is matching covered if each of its edges lies in a perfect matching. We say that an edge in a matching covered graph is removable if is matching covered. A pair of edges of a matching covered graph is a removable doubleton if is matching covered, but neither nor is. Removable edges and removable doubletons are called removable classes , introduced by Lovász and Plummer in connection with ear decompositions of matching covered graphs. A 3‐connected graph is a brick if the removal of any two distinct vertices, the left graph has a perfect matching. A brick is wheel‐like if has a vertex , such that every removable class of has an edge incident with . Lucchesi and Murty proposed a problem of characterizing wheel‐like bricks. We show that every wheel‐like brick may be obtained by splicing graphs whose underlying simple graphs are odd wheels in a certain manner. A matching covered graph is minimal if the removal of any edge, the left graph is not matching covered. Lovász and Plummer proved that the minimum degree of a minimal matching covered bipartite graph different from is 2 by ear decompositions in 1977. By the properties of wheel‐like bricks, we prove that the minimum degree of a minimal matching covered graph other than is either 2 or 3.