Generalizing Tutte’s theorem and maximal non-matchable graphs

A graph G has a perfect matching if and only if 0 is not a root of its matching polynomial μ ( G , x ) . Thus, Tutte’s famous theorem asserts that 0 is not a root of μ ( G , x ) if and only if c odd ( G − S ) ≤ | S | for all S ⊆ V ( G ) , where c odd ( G ) denotes the number of odd components of G . Tutte’s theorem can be proved using a characterization of the structure of maximal non-matchable graphs, that is, the edge-maximal graphs among those having no perfect matching. In this paper, we prove a generalized version of Tutte’s theorem in terms of avoiding any given real number θ as a root of μ ( G , x ) . We also extend maximal non-matchable graphs to maximal θ -non-matchable graphs and determine the structure of such graphs.