Bound the perfect matchings on a graph with n vertices where deg(v)=m for every vertex

Question

Hello everyone interested. This problem in the title is hard -i think- in its general case. The requirement is to bound the perfect matchings on a graph with n vertices where deg(v)=m for every vertex.

I tried considering the case say n=50 and m=deg(v)=2 for every vertex and tried by counting upwards for connected components. Got lost. What makes it hard is that we have no assumption on the graph.

Is there a way to provide a bound in this case? Even for the n=50 and deg(v)=2, I hope I can generalize the reasoning... Thanks in advance.

Answer 1

For the case where the graph is bipartite and every vertex has degree 2, the number of perfect matchings is easy to compute. Every even cycle has precisely two matchings. A bipartite graph where every vertex has degree 2 is a collection $\{C\}$ of vertex-disjoint even cycles (these are easy to find and count) and therefore has $2^{\#\{C\}|}$ perfect matchings, where $\{C\}$ is the set of cycles in $G$.

If $G$ is a bipartite graph w a perfect matching where the maximum degree is 2, then $G$ is a vertex-disjoint collection of cycles and paths with an even number of vertices in each (these are easy to find and count. Each even path has exactly one perfect matching. Thus, as before, $G$ has perfect $2^{\#\{C\}|}$ matchings

Answer 2

There are also some interesting results for regular graphs where vertices have degree higher than $2$.

One of the earliest theorems in graph theory is Petersen's theorem that a cubic ($3$-regular) bridgeless (every edge belongs to a cycle) graph has (at least) one perfect matching. The restriction to bridgeless graphs is necessary to this conclusion.

More generally a regular graph $G$ of degree $d$ with $d-1$ edge connectivity and an even number of vertices will always have a perfect matching, and every edge of $G$ belongs to at least one perfect matching. NB: When the degree $d$ is odd, assuming an even number of vertices is redundant because of the handshaking lemma.

It had long been conjectured that a cubic bridgeless graph on $n$ vertices will have exponentially many (in $n$) perfect matchings. After several people got partial results in this direction, Esperet et al (2011) succeeded in proving a lower bound of the claimed form.

The number of perfect matchings in a complete bipartite graph with equal partitions serves to establish the tightness of upper bounds given by S. Friedland (2008) in An upper bound for the number of perfect matchings in graphs. Taking as before the graph $G$ to be regular of degree $d$ with $n$ vertices, that upper bound simplifies to:

$$ \text{# of perfect matchings of }G \le (d!)^{\frac{n}{2d}} $$

Note that the number of perfect matchings in any bipartite graph with equal partitions is given by the permanent of its biadjacency matrix. A main building block in proving the bound above is the celebrated Bregman-Minc inequality for permanents of $\{0,1\}$-matrices.