Algebraic Matching Theory

The number of vertices missed by a maximum matching in a graph G is the multiplicity of zero as a root of the matchings polynomial ¯(G; x) of G, and hence many results in matching theory can be expressed in terms of this multiplicity. Thus, if mult(`; G) denotes the multiplicity of ` as a zero of ¯(G; x), then Gallai's lemma is equivalent to the assertion that if mult(`; Gnu) ! mult(`; G) for each vertex u of G, then mult(`; G) = 1. This paper extends a number of results in matching theory to results concerning mult(`; G), where ` is not necessarily zero. If P is a path in G then G n P denotes the graph got by deleting the vertices of P from G. We prove that mult(`; G n P ) mult(`; G) \Gamma 1, and we say P is `-essential when equality holds. We show that if, all paths in G are `-essential, then mult(`; G) = 1. We define G to be `-critical if all vertices in G are `-essential and mult(`; G) = 1. We prove that if mult(`; G) = k then there is an induced subgraph H with exactly k..