Matching polynomial

Matching polynomial --- полином паросочетаний.

Let [math]\displaystyle{ p(G,k) }[/math] be the number of matchings of the graph [math]\displaystyle{ G }[/math] with [math]\displaystyle{ k }[/math] edges. Then the matching polynomial of [math]\displaystyle{ G }[/math] is

[math]\displaystyle{ \mu(G,x) = \sum_{k=0}^{\lfloor n/2 \rfloor} (-1)^{k}p(G,k)x^{n-2k}. }[/math]

It is known that [math]\displaystyle{ \mu(G,k) }[/math] has only real roots.