An improved linear bound on the number of perfect matchings in cubic graphs
published by Daniel Kral
in 2009
and research's language is
English
Download
Abstract in English
We show that every cubic bridgeless graph with n vertices has at least 3n/4-10 perfect matchings. This is the first bound that differs by more than a constant from the maximal dimension of the perfect matching polytope.