# k! perfect matches

Let $G=($ $A \cup B$ , $E$ $)$ be a bipartite graph with perfect matching. Denote $|A| = n$. Prove that if every vertex in A has degree $\geq$ $k$ then G has at least $k!$ perfect matches.

I tried the following solution ,but It failed... I think I am just missing something really easy...I tried induction on both $|A|$ and $k$ . The base of the induction is trivial (|A| = 1 , then there is a perfect matching and we must have $k$=1, for general |A| if k=1 then there is a matching...). Lets move to the general case.

Let $a$ be some vertex of degree $k$ (if all the vertices are of degree $>k$ then take some vertex and remove edges that are incident to it and do not participate in the perfect matching. After we finish removing them we have a graph such that all the vertices on one side have degree at least $k$ and we have a vertex of degree k, plus G still contains the same perfect matching we had before removing edges). If we have that for each edge $e=(a,b)$ the graph $G'= G$-$\{a,b\}$(deleting both $a$ and $b$ from $G$) we still have perfect matching then by induction we have in $G'$ $(k-1)!$ perfect matches . By adding to each matching the edge $e$ we get a matching of $G$ , since $deg(a)=k$ we get $k!$ matchings.

O.w. we have that there exist an edge such that $G'$ doesn't have perfect matching. Using Konig's theorem (the size of maximum matching in bipartite graph is equal to the minimum size of vertex cover) we get that in $G'$ the minimum vertex cover is of size at most $n-2$. If it has a vertex cover of size $n-3$ then by joining $a$ and $b$ to the vertex cover we would get a vertex cover of size $n-1$ for G , in contradiction to the assumption that the minimal vertex cover is $n$ (again , by Konig's theorem).

So we get that there is a vertex cover $T$ of size $n-2$ in $G'$, and it is minimal. If all the neighbours of $a$ or $b$ reside in $T$, then by joining only one vertex from $\{a,b\}$ we would get a vertex cover of size $n-1$ ,which is a contradiction. So we can assume that there are vertices $a_2 , b_2$, both not in T , such that $(a_2,b),(a,b_2) \in E$. But here I got stuck. I also tried using Hall's theorem , but again , I got nowhere. I'll be happy if you could give me an hint about what to do.

I provide a complete answer here. I try to give them in a "hint"-ish order, so that you can just read a prefix of my answer for a hint.

Suppose the minimum degree is $k$. I will show that there must exist a node $a \in A$ such that there exists at least $k$ different nodes $b \in B$, such that there exists a perfect matching in $G$ that includes $(a, b)$. Thus, you can obtain $k!$ perfect matching by induction: from the graph $G$, pick $a \in A$ as described above. For every $b \in B$ such that $(a, b)$ is a member of at least one perfect matching, consider the graph $G' = (A \cup B - a - b, E)$ (that is, we remove nodes $a$ and $b$ and all edges adjacent to them from $G$). Clearly $G'$ has a perfect matching and all of its nodes have degree at least $k-1$, so it contains $(k-1)!$ perfect matching by the inductive hypothesis. Since there exists at least $k$ such node $b$, the total number of matchings is $k \times (k-1)! = k!$.

Now I show that there must exist a node $a \in A$ such that there exists at least $k$ different nodes $b \in B$, such that there exists a perfect matching in $G$ that includes $(a, b)$. I prove by contradiction. Find the smallest $k$ for which this may not hold. Clearly $k > 1$. In this case, for every node $a' \in A$, there must exists $b' \in B$ such that $(a', b') \in E$ and that $(a', b')$ cannot be a member of a perfect matching. This is true since the degree of $a'$ is at least $k$, but there can only be at most $k-1$ different nodes $b \in B$ such that there exists a perfect matching in $G$ that includes $(a', b)$. Define the function $f: A \to B$ by $f(a') = b'$ as defined above (if there are more than one such $b'$, this function just pick one arbitrarily).

Let $P \subset E$ be any perfect matching of $G$. Define the function $g: B \to A$ such that $g(b) = a$ iff $(a, b) \in P$ (that is, $g$ maps each member of $B$ to its match in $A$ according to the matching $P$). Let $a \in A$ be any node in $A$.

Consider the following sequence $S$:

• $s_1 = a$
• $s_i = g(f(s_{i-1}))$ for $i > 1$

$S$ will be an infinite sequence of nodes in $A$. Since $A$ is finite, there will exist $1 \le i < j$ such that $s_i = s_j$ (the node repeats). Pick the smallest such $i$, and then the smallest such $j$. Let $O = \{(g(f(s_k)), f(s_k)) | i \le k < j\}$ and $O' = \{(s_k, f(s_k)) | i \le k < j\}$. Clearly $O$ and $O'$ contains the same number of elements, and contains the exact same set of nodes. In addition, $O \subseteq P$ and $O' \cap P = \emptyset$. Thus, $P - O + O'$ is a perfect matching of $G$. But this contradicts the fact that none of the members of $O'$ can be included in any perfect matching. This completes the proof.

• It is a proof, and indeed a good one , but I think it is not elegant enough. I hope a more elegant solution will show up :\ (maybe one that uses my idea) – UserB95 Jul 30 '15 at 13:21