The maximum number of edges in minimal matching covered graphs

Abstract

A connected graph $G$ with at least two vertices is {\em matching covered} if each of its edges lies in a perfect matching. A matching covered graph is {\em minimal} if the removal of any edge results in a graph that is no longer matching covered. Lov\'asz and Plummer [J. Combin. Theory, Ser. B 23 (1977) 127--138] proved by ear decompositions that every minimal matching covered bipartite graph $G$ different from $K_2$ has at most $(3|V(G)|-6)/2$ edges, and this bound is sharp for all $|V(G)|\ge4$. In this paper, we prove that every minimal matching covered nonbipartite graph $G$ with at least 6 vertices has at most $5(|V(G)|-2)/2$ edges, and this bound is sharp for all $|V(G)|\ge6$.