Understanding Deletion Contraction for Matching Polynomials

101 Views Asked by At

For matching polynomials we have the relation $M_{G}(x) = M_{G-e}(x) + xM_{G-\overline{e}}(x)$ where $G-e$ is standard notation for the removal of any edge from the graph $G$ and $G-\overline{e}$ denotes the removal of the edge $e$ and its attached vertices call them $v$ and $w$ s.t. $G-\overline{e} = G - \{v,w\}$.

I am able to rationalize the relation for $x=1$ which yields the total number of matchings in the graph like so:

  • $M_G(1)$ denotes the total number of matchings in the graph $G$ with or without the edge $e$

  • $M_{G-e}(1)$ denotes the total number of matchings in the graph $G$ which do not contain the edge e

  • $M_{G-\overline{e}}(1)$ denotes the total number of matchings in the graph $G$ which include the edge $e \implies$ they do not include the vertices $\{v,w\}$.

Thus the conclusion that follows is $M_{G}(1) = M_{G-e}(1) + 1 \times M_{G-\overline{e}}(1)$, a special case of the general relation. $\square$

Why does the general relation require multiplying by $x$ for the $G-\overline{e}$ term?

I assume it has to do with the degree of the polynomial yielding the matching number of $G$, the maximum number for which $M_n(G) \neq 0$ where $M_n(G)$ denotes the number of matchings with $n$ edges in $G$, but I cannot see how.

1

There are 1 best solutions below

0
On BEST ANSWER

The coefficient of $x^k$ in the polynomial is the number of $k$-edge matchings.

Since the number of $k$-edge matchings in $G$ which include $e$ is equal to the number of $(k-1)$-edge matchings in $G-\overline{e}$, we want to multiply $M_{G-\overline e}(x)$ by $x$ to make sure that the $x^{k-1}$ term of $M_{G-\overline e}(x)$ contributes to the $x^k$ term of $M_G(x)$.