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*}

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).)

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{:}\)

   

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.

   

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{?}\)

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

   3. Why does part (ii) guarantee that \(|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{.}\)

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

   3. Find a perfect matching in \(H\text{.}\) Why does part (a) guarantee that \(H = G-M\) 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.

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{?}\)

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.

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?

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.