Matching polynomials of vertex transitive graphs

Let G be a graph of order n. Denote by p(G,k) the number of k-matchings in G. The matching polynomial of G is defined as 

       μ(G,x) = Σ (-1)k p(G,k) xn-2k

where the sum runs from 0 to [n/2]. It is known that every matching polynomial has only real roots. See [1,2].

Some time ago I made the following

Conjecture: For every integer r there exists a vertex transitive graph G whose matching polynomial has a root of multiplicity at least r.

It would be interesting to find a vertex transitive graph whose matching polynomial has a nonsimple root. Such a graph would not have a hamiltonian path (see [1,2]) and would disprove a conjecture of Lovasz that every vertex transitive graph has a hamiltonian path.


[1] Heilmann, Ole J.; Lieb, Elliott H. Theory of monomer-dimer systems. Comm. Math. Phys. 25 (1972), 190-232.

[2] Godsil, C. D.; Gutman, I. On the theory of the matching polynomial. J. Graph Theory 5 (1981), 137-144.

Send comments to

Revised: junij 15, 2001.