4.5: Matching in Bipartite Graphs
- Page ID
- 14769
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)
\( \def\d{\displaystyle}\)
\( \newcommand{\f}[1]{\mathfrak #1}\)
\( \newcommand{\s}[1]{\mathscr #1}\)
\( \def\N{\mathbb N}\)
\( \def\B{\mathbf{B}}\)
\( \def\circleA{(-.5,0) circle (1)}\)
\( \def\Z{\mathbb Z}\)
\( \def\circleAlabel{(-1.5,.6) node[above]{$A$}}\)
\( \def\Q{\mathbb Q}\)
\( \def\circleB{(.5,0) circle (1)}\)
\( \def\R{\mathbb R}\)
\( \def\circleBlabel{(1.5,.6) node[above]{$B$}}\)
\( \def\C{\mathbb C}\)
\( \def\circleC{(0,-1) circle (1)}\)
\( \def\F{\mathbb F}\)
\( \def\circleClabel{(.5,-2) node[right]{$C$}}\)
\( \def\A{\mathbb A}\)
\( \def\twosetbox{(-2,-1.5) rectangle (2,1.5)}\)
\( \def\X{\mathbb X}\)
\( \def\threesetbox{(-2,-2.5) rectangle (2,1.5)}\)
\( \def\E{\mathbb E}\)
\( \def\O{\mathbb O}\)
\( \def\U{\mathcal U}\)
\( \def\pow{\mathcal P}\)
\( \def\inv{^{-1}}\)
\( \def\nrml{\triangleleft}\)
\( \def\st{:}\)
\( \def\~{\widetilde}\)
\( \def\rem{\mathcal R}\)
\( \def\sigalg{$\sigma$-algebra }\)
\( \def\Gal{\mbox{Gal}}\)
\( \def\iff{\leftrightarrow}\)
\( \def\Iff{\Leftrightarrow}\)
\( \def\land{\wedge}\)
\( \def\And{\bigwedge}\)
\( \def\entry{\entry}\)
\( \def\AAnd{\d\bigwedge\mkern-18mu\bigwedge}\)
\( \def\Vee{\bigvee}\)
\( \def\VVee{\d\Vee\mkern-18mu\Vee}\)
\( \def\imp{\rightarrow}\)
\( \def\Imp{\Rightarrow}\)
\( \def\Fi{\Leftarrow}\)
\( \def\var{\mbox{var}}\)
\( \def\Th{\mbox{Th}}\)
\( \def\entry{\entry}\)
\( \def\sat{\mbox{Sat}}\)
\( \def\con{\mbox{Con}}\)
\( \def\iffmodels{\bmodels\models}\)
\( \def\dbland{\bigwedge \!\!\bigwedge}\)
\( \def\dom{\mbox{dom}}\)
\( \def\rng{\mbox{range}}\)
\( \def\isom{\cong}\)
\(\DeclareMathOperator{\wgt}{wgt}\)
\( \newcommand{\vtx}[2]{node[fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2]{}}\)
\( \newcommand{\va}[1]{\vtx{above}{#1}}\)
\( \newcommand{\vb}[1]{\vtx{below}{#1}}\)
\( \newcommand{\vr}[1]{\vtx{right}{#1}}\)
\( \newcommand{\vl}[1]{\vtx{left}{#1}}\)
\( \renewcommand{\v}{\vtx{above}{}}\)
\( \def\circleA{(-.5,0) circle (1)}\)
\( \def\circleAlabel{(-1.5,.6) node[above]{$A$}}\)
\( \def\circleB{(.5,0) circle (1)}\)
\( \def\circleBlabel{(1.5,.6) node[above]{$B$}}\)
\( \def\circleC{(0,-1) circle (1)}\)
\( \def\circleClabel{(.5,-2) node[right]{$C$}}\)
\( \def\twosetbox{(-2,-1.4) rectangle (2,1.4)}\)
\( \def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)}\)
\( \def\ansfilename{practice-answers}\)
\( \def\shadowprops{ {fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge 10 percent}} }\)
\( \renewcommand{\bar}{\overline}\)
\( \newcommand{\card}[1]{\left| #1 \right|}\)
\( \newcommand{\twoline}[2]{\begin{pmatrix}#1 \\ #2 \end{pmatrix}}\)
\( \newcommand{\lt}{<}\)
\( \newcommand{\gt}{>}\)
\( \newcommand{\amp}{&}\)
\( \newcommand{\hexbox}[3]{
\def\x{-cos{30}*\r*#1+cos{30}*#2*\r*2}
\def\y{-\r*#1-sin{30}*\r*#1}
\draw (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- cycle;
\draw (\x,\y) node{#3};
}\)
\(\renewcommand{\bar}{\overline}\)
\(\newcommand{\card}[1]{\left| #1 \right|}\)
\(\newcommand{\twoline}[2]{\begin{pmatrix}#1 \\ #2 \end{pmatrix}}\)
\(\newcommand{\lt}{<}\)
\(\newcommand{\gt}{>}\)
\(\newcommand{\amp}{&}\)
Investigate!
Given a bipartite graph, a matching is a subset of the edges for which every vertex belongs to exactly one of the edges. Our goal in this activity is to discover some criterion for when a bipartite graph has a matching.
Does the graph below contain a matching? If so, find one.
Not all bipartite graphs have matchings. Draw as many fundamentally different examples of bipartite graphs which do NOT have matchings. Your goal is to find all the possible obstructions to a graph having a perfect matching. Write down the necessary conditions for a graph to have a matching (that is, fill in the blank: If a graph has a matching, then ). Then ask yourself whether these conditions are sufficient (is it true that if , then the graph has a matching?).
We conclude with one more example of a graph theory problem to illustrate the variety and vastness of the subject.
Suppose you have a bipartite graph \(G\text{.}\) This will consist of two sets of vertices \(A\) and \(B\) with some edges connecting some vertices of \(A\) to some vertices in \(B\) (but of course, no edges between two vertices both in \(A\) or both in \(B\)). A matching of \(A\) is a subset of the edges for which each vertex of \(A\) belongs to exactly one edge of the subset, and no vertex in \(B\) belongs to more than one edge in the subset. In practice we will assume that \(|A| = |B|\) (the two sets have the same number of vertices) so this says that every vertex in the graph belongs to exactly one edge in the matching. 5 Note: what we are calling a matching is sometimes called a perfect matching or complete matching. This is because in it interesting to look at non-perfect matchings as well. We will call those partial matchings.
Some context might make this easier to understand. Think of the vertices in \(A\) as representing students in a class, and the vertices in \(B\) as representing presentation topics. We put an edge from a vertex \(a \in A\) to a vertex \(b \in B\) if student \(a\) would like to present on topic \(b\text{.}\) Of course, some students would want to present on more than one topic, so their vertex would have degree greater than 1. As the teacher, you want to assign each student their own unique topic. Thus you want to find a matching of \(A\text{:}\) you pick some subset of the edges so that each student gets matched up with exactly one topic, and no topic gets matched to two students. 6 The standard example for matchings used to be the marriage problem in which \(A\) consisted of the men in the town, \(B\) the women, and an edge represented a marriage that was agreeable to both parties. A matching then represented a way for the town elders to marry off everyone in the town, no polygamy allowed. We have chosen a more progressive context for the sake of political correctness.
The question is: when does a bipartite graph contain a matching of \(A\text{?}\) To begin to answer this question, consider what could prevent the graph from containing a matching. This will not necessarily tell us a condition when the graph does have a matching, but at least it is a start.
One way \(G\) could not have a matching is if there is a vertex in \(A\) not adjacent to any vertex in \(B\) (so having degree 0). What else? What if two students both like the same one topic, and no others? Then after assigning that one topic to the first student, there is nothing left for the second student to like, so it is very much as if the second student has degree 0. Or what if three students like only two topics between them. Again, after assigning one student a topic, we reduce this down to the previous case of two students liking only one topic. We can continue this way with more and more students.
It should be clear at this point that if there is every a group of \(n\) students who as a group like \(n-1\) or fewer topics, then no matching is possible. This is true for any value of \(n\text{,}\) and any group of \(n\) students.
To make this more graph-theoretic, say you have a set \(S \subseteq A\) of vertices. Define \(N(S)\) to be the set of all the neighbors of vertices in \(S\text{.}\) That is, \(N(S)\) contains all the vertices (in \(B\)) which are adjacent to at least one of the vertices in \(S\text{.}\) (In the student/topic graph, \(N(S)\) is the set of topics liked by the students of \(S\text{.}\)) Our discussion above can be summarized as follows:
Matching Condition
If a bipartite graph \(G = \{A, B\}\) has a matching of \(A\text{,}\) then
\begin{equation*} |N(S)| \ge |S| \end{equation*}for all \(S \subseteq A\text{.}\)
Is the converse true? Suppose \(G\) satisfies the matching condition \(|N(S)| \ge |S|\) for all \(S \subseteq A\) (every set of vertices has at least as many neighbors than vertices in the set). Does that mean that there is a matching? Surprisingly, yes. The obvious necessary condition is also sufficient. 7 This happens often in graph theory. If you can avoid the obvious counterexamples, you often get what you want. This is a theorem first proved by Philip Hall in 1935. 8 There is also an infinite version of the theorem which was proved by Marshal Hall, Jr. The name is a coincidence though as the two Halls are not related.
Theorem4.5.1Hall's Marriage Theorem
Let \(G\) be a bipartite graph with sets \(A\) and \(B\text{.}\) Then \(G\) has a matching of \(A\) if and only if
\begin{equation*} |N(S)| \ge |S| \end{equation*}for all \(S \subseteq A\text{.}\)
There are quite a few different proofs of this theorem – a quick internet search will get you started.
In addition to its application to marriage and student presentation topics, matchings have applications all over the place. We conclude with one such example.
Example \(\PageIndex{1}\)
Suppose you deal 52 regular playing cards into 13 piles of 4 cards each. Prove that you can always select one card from each pile to get one of each of the 13 card values Ace, 2, 3, …, 10, Jack, Queen, and King.
- Solution
-
Doing this directly would be difficult, but we can use the matching condition to help. Construct a graph \(G\) with 13 vertices in the set \(A\text{,}\) each representing one of the 13 card values, and 13 vertices in the set \(B\text{,}\) each representing one of the 13 piles. Draw an edge between a vertex \(a \in A\) to a vertex \(b \in B\) if a card with value \(a\) is in the pile \(b\text{.}\) Notice that we are just looking for a matching of \(A\text{;}\) each value needs to be found in the piles exactly once.
We will have a matching if the matching condition holds. Given any set of card values (a set \(S \subseteq A\)) we must show that \(|N(S)| \ge |S|\text{.}\) That is, the number of piles that contain those values is at least the number of different values. But what if it wasn't? Say \(|S| = k\text{.}\) If \(|N(S)| < k\text{,}\) then we would have fewer than \(4k\) different cards in those piles (since each pile contains 4 cards). But there are \(4k\) cards with the \(k\) different values, so at least one of these cards must be in another pile, a contradiction. Thus the matching condition holds, so there is a matching, as required.