# #perfectMatchings is self-reducible

How can one show that the counting problem:

Given a graph, output the number of perfect matchings

Is self reducible?

I found a hint in Moore's Chapter on Counting, Sampling and Statistical Physics:

Let G be a graph and e one of its edges. Show that we can modify G to produce two graphs, G0 and G1, such that the number of perfect matchings of G that include and exclude e is the number of perfect matchings of G1 and G0 respectively.

But I could not come up with a proof. The main question here is: How can we proof self-reducability of #perfectMatchings?

Aside: I don't know of a formal definition of self-reduciability. I just know the intuitive phrasing "partially solving the problem results in a smaller problem of the same kind". But is there a formal definition?

## 1 Answer

To count all perfect matchings containing an edge $$e = (x,y)$$, simply remove both endpoints $$x,y$$. To count all perfect matching not containing the edge $$e$$, simply remove the edge.

• Thanks, this makes sense. Just that I got the notion of self-reducibility correct: As in both cases, the number of edges decreases by at least 1, it is self-reducible? Commented Nov 19, 2020 at 9:41
• Self-reducibility is a somewhat informal notion, though there might be formalizations floating around in some papers. Commented Nov 19, 2020 at 9:43