Discrete Mathematics: Activities and Exercises

1. Bipartite Graphs and Neighborhoods.

A graph \(G = (V,E)\) is bipartite if \(V= A \cup B\) where \(A \cap B = \emptyset\) and every edge \(e \in E\) runs between these two sets. Equivalently: we can color the vertices with two colors, (red and blue) so that adjacent vertices receive different colors.

1. Let \(G\) be any bipartite graph on vertices \(V = A \cup B\text{.}\) Explain why

   \begin{equation*} \sum_{v \in A} \deg (v) = \sum_{w \in B} \deg(w). \end{equation*}

   Solution.

   Since the edges run between \(A\) and \(B\text{,}\) each of these sums counts every edge once. That is,

   \begin{equation*} \sum_{v \in A} \deg (v) = |E| = \sum_{w \in B} \deg(w). \end{equation*}

2. Recall that a graph is \(d\)-regular when every vertex has degree \(d\text{.}\) Let \(G\) be a \(d\)-regular bipartite graph on partite sets \(A,B\text{.}\) Prove that \(|A|=|B|\text{.}\) (Hint: use part (a).) Solution.

   Since every vertex has degree equal to \(d\text{,}\) Problem 1(b) means that

   \begin{equation*} d |A| = \sum_{v \in A} \deg (v) = |E| = \sum_{w \in B} \deg(w) = d |B| \end{equation*}

   and therefore \(|A|=|B|\text{.}\)

3. Let \(G=(V,E)\) be a bipartite graph on vertices \(V=A \cup B\text{.}\) Given a set of vertices \(S \subset A\text{,}\) we define the neighborhood \(N(S) \subset B\) to be the set of vertices that are adjacent to some vertex in \(A\text{.}\) That is,

   \begin{equation*} \mbox{if } S \subset A \mbox{ then } N(S) = \{ b \in B : \exists a \in A, (a,b) \in E \} . \end{equation*}

   For each of the examples below, find the neighborhood \(N(S) \subset B\text{:}\)

   
   Solution.

   

2. Perfect Matchings.

Given a bipartite graph \(G= (V,E)\) where \(V=A \cup B\) and \(|A|=|B|\text{,}\) a perfect matching \(M\) is a disjoint set of edges that uses every vertex.

1. For each of the graphs below, find a perfect matching or explain why no such matching exists.

   
   Solution.

   

3. Hall's Matching Theorem for a \(d\)-regular graph.

Here is Hall's Matching Theorem: Given a bipartite graph with \(V = A \cup B\) and \(|A|=|B|\text{.}\) Then

\(G\) has a perfect matching \(\Longleftrightarrow\) for every \(S \subset A\text{,}\) we have \(|S| \leq |N(S)|\text{.}\)

The last statement is called Hall's Condition. It means that "\(G\) has no bottlenecks."

1. Let \(G=(V,E)\) be a \(d\)-regular bipartite graph. By Problem 1(b), we have \(|A|=|B|\text{.}\) You will show that Hall's condition holds for \(G\text{.}\) This means that a \(d\)-regular bipartite graph always has a perfect matching.

   1. Pick any subset \(S \subset A\text{.}\) What is \(\sum_{v \in S} \deg(v)\text{?}\) Solution.

      \begin{equation*} \sum_{v \in S} \deg(v) = d |S| \end{equation*}

   2. Explain why \(\displaystyle{\sum_{v \in S} \deg(v) \leq \sum_{v \in N(S)} \deg(v)}\text{.}\)

      Solution.

      Every edge from a vertex in set \(S\) ends at a vertex in \(N(S)\text{.}\) This confirms that

      \begin{equation*} \sum_{v \in S} \deg(v) \leq \sum_{v \in N(S)} \deg(v). \end{equation*}

      Note that this inequality can be strict: vertices in \(N(S)\) may have neighbors outside of the set \(S\text{.}\)

   3. Why does part (ii) guarantee that \(|S| \leq |N(S)|\text{?}\) Solution.

      \begin{equation*} d |S| = \sum_{v \in S} \deg(v) \leq \sum_{v \in N(S)} \deg(v) = d|N(S)| \end{equation*}

      and so \(|S| \leq |N(S)|\text{.}\)

2. Here is a 3-regular bipartite graph \(G\) on 6 vertices.

   

   1. Find a perfect matching \(M\) in the graph \(G\text{.}\) Solution.

      

   2. Now draw the graph \(H=G-M\) where you remove the edges in your matching \(M\text{.}\) Solution.

      

   3. Find a perfect matching in \(H\text{.}\) Why does part (a) guarantee that \(H = G-M\) has a perfect matching? Solution.

      

      \(G-M\) is a 2-regular graph. So it has a perfect matching.

3. Let \(G\) be a \(d\)-regular bipartite graph where \(|A|=|B|=n\text{.}\) Use (regular) induction on \(d \geq 1\) to prove that a \(d\)-regular bipartite graph has \(d\) disjoint perfect matchings. This means that we can color the edges of \(G\) using \(d\) colors so that every vertex is incident with exactly one edge from each of the \(d\) colors. Solution.

   • Base Case: \(d=1\text{.}\)

     A 1-regular graph is a perfect matching!

   • Inductive Hypothesis: Assume that if \(G\) is a \((d-1)\)-regular bipartite graph where \(|A|=|B|=n\text{,}\) then \(G\) has \(d-1\) disjoint perfect matchings. \((\star)\)

   • Inductive Step: Use \((\star)\) to prove that if \(G\) is a \(d\)-regular bipartite graph where \(|A|=|B|=n\text{,}\) then \(G\) has \(d\) disjoint perfect matchings.

   By part (a), The \(d\)-regular bipartite graph \(G\) has a perfect matching \(M\text{.}\) Let's remove these edges. The graph \(G-M\) is \((d-1)\)-regular. By \((\star)\text{,}\) \(G-M\) has \(d-1\) disjoint perfect matchings. So we have found \(d\) disjoint perfect matchings.

4. A Mathematical Card Trick.

Here is a mathematical card trick whose secret uses a perfect matching in a bipartite graph! In a standard deck of 52 cards, each card has a suit and a value. There are 4 suits (clubs, diamonds, hearts, spades) and 13 values (A, 2, 3, . . . , 10, J, Q, K).

Ask a volunteer (or your worst enemy) to lay out the cards into a grid of 4 rows and 13 columns. Show that you can always pick out 13 cards, one from each column of the grid, so that you end up with a card for every possible value \(A, 2, 3, \ldots , 10 , J, Q, K\text{.}\) Wow!!! Here is an example. The 13 cards I've chosen are highlighted.

1. You can model this trick using a bipartite graph \(G\) with \(|A| = |B| = 13\text{.}\)

   • Let \(A\) be the set of 13 card values \(\{A, 2, 3, \ldots, 10, J, Q, K \}\)

   • Let \(B\) be the set of columns \(\{1, 2, 3, \ldots, 13\}\text{.}\)

   When should a card in set \(A\) have an edge to a column in set \(B\text{?}\) What is the degree of a vertex in \(A\text{?}\) What is the degree of a vertex in \(B\text{?}\)

   Solution.

   Add an edge from a value \(v\) to a column \(c\) whenever a card with value \(v\) appears in column \(c\text{.}\) Crucially, we will need to create a multigraph where we can have multiple edges between vertices. This results in a 4-regular bipartite multigraph.

2. Use a previous problem from this activity to show that your graph \(G\) always has a perfect matching. Then explain why this matching finds 13 cards with distinct values spread among the 13 columns. Solution.

   Problem 1(b) applies to a \(d\)-regular multigraph. So we can find a perfect matching in our graph. This perfect matching corresponds to the 13 cards that we desire.

3. Are you guaranteed to be able to do it again? That is, from the remaining 39 cards, can you find \(A, 2, \ldots, K\text{,}\) one card in each column? Why or why not? Solution.

   Yes! Removing this matching results in a 3-regular graph. So we can do it again to find a disjoint set of 13 cards with the same property. In fact we can do it a final two times as well! So we can find four disjoint solutions to the magic trick!

5. Finding a Perfect Matching.

Use this algorithm to find a perfect matching in a bipartite graph \(G\) with \(V=A \cup B\text{.}\)

• Start with \(M = \emptyset\text{.}\)

• Greedy Phase

  • Add disjoint edges to \(M\) until you get stuck.

  • If you have a perfect matching, then you are done!

  • If not, then move onto the Augmenting Phase.

• Augmenting phase

  • Pick any unmatched vertex \(a \in A\text{.}\)

  • Try to find an alternating path \(P\) to an unmatched vertex \(b \in B\text{.}\) The edges in path \(P\) alternately come from the set \(E \backslash M\) and the set \(M\text{.}\)

  • If you cannot find such a path, then you are stuck. There is no matching.

  • If you find such a path, then swap the matching edges of \(P\) and the non-matching edges of \(P\) to get a bigger matching.

  • Repeat (a) - (d) until you are either stuck, or all vertices are matched!

Here is an example. We start with the following bipartite graph

1. Use the alternating path algorithm to find a perfect matching for this graph, starting from the 4-edge matching shown in the first graph.

   
   Solution.