Generalization of Marshall Hall's Theorem to non-simple bipartite graphs

Question

Lemma 8.6.5 of the book "Matching Theory" by Lovász and Plummer states the following lemma:

Lemma: Let $G$ be a simple bipartite graph with bipartition $(A,B)$, and assume that each point in $A$ has degree at least $k$. Then if $G$ has at least one perfect matching, it has at least $k!$ perfect matchings.

From this lemma, we can obviously deduce the following theorem:

Theorem 1: If $G$ is a matchable simple bipartite graph with $\deg~(v)\ge d$ for all $v\in V(G)$, then $G$ has at least $d!$ distinct perfect matchings.

I was wondering if we can generalize Theorem 1 to non-simple bipartite graphs. Note that the generalization does not hold true for the $n$-regular graph on two vertices, which has exactly $n$ perfect matchings instead of at least $n!$ perfect matchings.

For all $k\ge 3$, define $\mathcal{C}_k$ to be the set of $k$-regular graphs $C$ such that for each vertex $v\in V(C)$, there exists two distinct vertices (in $V(C)$) $x\neq v,y\neq v$ with exactly $k-1$ edges between $v$ and $x$, and exactly an edge between $v$ and $y$. Note that for any $k\ge 3$, if $C\in\mathcal{C}_k$ has $2n$ vertices, then it has exactly $(k-1)^n+1$ perfect matchings. So, for any $C\in\mathcal{C}_k$, if $C$ has $2n$ vertices, then it agrees with the generalization of Theorem 1 if and only if $(k-1)^n+1>k!$.

Now, for any $k\ge 3$, select any $C\in \mathcal{C}_k$, and any $a,b\in V(C)$ such that there exists exactly one edge between $a$ and $b$. Note that for all $v\in V(C-a-b)$, $\deg(v)\ge 1$, and $C-a-b$ has exactly one perfect matching. Hence, it agrees with the generalisation of Theorem 1.

These observations leads us to the following conjecture:

Conjecture: Except for a finite number of special infinite families of graphs, if $G$ is a matchable non-simple bipartite graph with $\deg (v)\ge d$ for all $v\in V(G)$, then $G$ has at least $d!$ perfect matchings.

So, is there any result already in the literature which is similar to the above conjecture?

Any help along these lines would be of high help. Thanks in advance!

Answer 1

As I mentioned in the comments, I am not exactly sure what "a finite number of special infinite families of graphs" means, but here is a way to construct an infinite number of counterexamples for all $d$.

Let $G$ be the half graph. This is the bipartite graph with vertices $u_1, \dots, u_n$ and $v_1, \dots, v_n$, where $u_i$ is adjacent to $v_i$ if and only if $i \leq j$. It is easy to see $M:=\{u_1v_1, \dots, u_nv_n\} $ is the unique perfect matching of $G$. Let $M':=M \setminus \{u_1v_1, u_nv_n\}$ and $G'$ be the multigraph obtained from $G$ by replacing each edge in $E(G) \setminus M'$ by $d$ parallel edges. Then $G'$ has minimum degree $d$, but only $d^2$ perfect matchings.

We can modify the example so that we add a huge number of parallel edges if $e \in E(G) \setminus M$, and $d$ parallel edges if $e \in \{u_1v_1, u_nv_n\}$. This creates a graph with only $d^2$ perfect matchings, all of whose vertices have arbitrary large degree (except for $u_1$ and $v_n$ which have degree $d$). Instead of using $E(G) \setminus M$ in the above construction, we can also use any subset $A \subseteq E(G) \setminus M$ such that all vertices in $G \setminus \{v_1, u_n\}$ are incident to at least one vertex of $A$.