A graph with at least two vertices is matching covered if it is connected and each edge lies in some perfect matching. A matching covered graph G is extremal if the number of perfect matchings of G is equal to the dimension of the lattice spanned by the set of incidence vectors of perfect matchings of G. We first establish several basic properties of extremal matching covered graphs. In particular, we show that every extremal brick may be obtained by splicing graphs whose underlying simple graphs are odd wheels. Then, using the main theorem proved in 2 and 3, we find all the extremal cubic matching covered graphs.
No takes yet. Share an insight, caveat, or question.
Carvalho et al. (2004) studied this question.
Synapse has enriched one closely related paper. Consider it for comparative context: