Generalizing Tutte’s theorem and maximal non-matchable graphs

A graph GG has a perfect matching if and only if 00 is not a root of its matching polynomial μ(G,x)μ(G,x). Thus, Tutte’s famous theorem asserts that 00 is not a root of μ(G,x)μ(G,x) if and only if codd(G−S)≤|S| for all S⊆V(G)S⊆V(G), where codd(G) denotes the number of odd components of GG. 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)μ(G,x). We also extend maximal non-matchable graphs to maximal θθ-non-matchable graphs and determine the structure of such graphs.