3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – UserB95 Jul 30 '15 at 13:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.