maths.free › Combinatorics & Graph Theory › 3. Graph Theory › Matching in Bipartite Graphs

Matching in Bipartite Graphs

Investigation Given a bipartite graph, a matching is a subset of the edges for which every vertex belongs to exactly one of the edges.

Matching in Bipartite Graphs

Investigation

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 criteria 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 that 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\). 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. What we are calling a matching is sometimes called a perfect matching or complete matching. This is because it is interesting to look at non-perfect matchings as well. We will call those partial matchings.

The question is: when does a bipartite graph contain a matching of \(A\)? 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.

It should be clear at this point that if there is 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\), and any group of \(n\) students.

If a bipartite graph \(G = \{A, B\}\) has a matching of \(A\), then \[|N(S)| \ge |S|\] for all \(S \subseteq A\).

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

Practice (6)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

  1. Find a matching of the bipartite graphs below or explain why no matching exists.

    Avslöja svaret

    The first and third graphs have a matching, shown in bold (there are other matchings as well). The middle graph does not have a matching. If you look at the three circled vertices, you see that they only have two neighbors, which violates the matching condition \(\card{N(S)} \ge \card{S}\) (the three circled vertices form the set \(S\)).

  2. A bipartite graph that doesn't have a matching might still have a partial matching. By this we mean a set of edges for which no vertex belongs to more than one edge (but possibly belongs to none). Every bipartite graph (with at least one edge) has a partial matching, so we can look for the largest partial matching in a graph.

    Your friend claims that she has found the largest partial matching for the graph below (her matching is in bold). She explains that no other edge can be added, because all the edges not used in her partial matching are connected to matched vertices. Is she correct?

  3. One way you might check to see whether a partial matching is maximal is to construct an alternating path. This is a sequence of adjacent edges, which alternate between edges in the matching and edges not in the matching (no edge can be used more than once). If an alternating path starts and stops with an edge not in the matching, then it is called an augmenting path.

    1. Find the largest possible alternating path for the partial matching of your friend's graph. Is it an augmenting path? How would this help you find a larger matching?

    2. Find the largest possible alternating path for the partial matching below. Are there any augmenting paths? Is the partial matching the largest one that exists in the graph?

  4. The two richest families in Westeros have decided to enter into an alliance by marriage. The first family has 10 sons, the second has 10 girls. The ages of the kids in the two families match up. To avoid impropriety, the families insist that each child must marry someone either their own age, or someone one position younger or older. In fact, the graph representing agreeable marriages looks like this:

    The question: how many different acceptable marriage arrangements which marry off all 20 children are possible?

    1. How many marriage arrangements are possible if we insist that there are exactly 6 boys who marry girls not their own age?

    2. Could you generalize the previous answer to arrive at the total number of marriage arrangements?

    3. How do you know you are correct? Try counting in a different way. Look at smaller family sizes and get a sequence.

    4. Can you give a recurrence relation that fits the problem?

  5. We say that a set of vertices \(A \subseteq V\) is a vertex cover if every edge of the graph is incident to a vertex in the cover (so a vertex cover covers the edges). Since \(V\) itself is a vertex cover, every graph has a vertex cover. The interesting question is about finding a minimal vertex cover, one that uses the fewest possible number of vertices.

    1. Suppose you had a matching of a graph. How can you use that to get a minimal vertex cover? Will your method always work?
    2. Suppose you had a minimal vertex cover for a graph. How can you use that to get a partial matching? Will your method always work?
    3. What is the relationship between the size of the minimal vertex cover and the size of the maximal partial matching in a graph?

  6. For many applications of matchings, it makes sense to use bipartite graphs. You might wonder, however, whether there is a way to find matchings in graphs in general.

    1. \(n\)\(K_n\)
    2. \(\card{V}\)
    3. \(\card{V}\)
    4. \(\card{N(S)} \ge \card{S}\)\(S \subseteq V\)

Symbols used here

x \in A,\ A \subseteq B
element of, subset
x belongs to A; every element of A is in B.
\leq,\ \geq
less/greater than or equal
Inequalities that allow equality; < and > exclude it.
n!
factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.
\binom{n}{k}
binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).
\sum_{k=1}^{n} a_k
summation
Add a_k for k = 1 up to n.
\prod_{k=1}^{n} a_k
product
Multiply a_k for k = 1 up to n.
\emptyset,\ |A|
empty set, cardinality
The set with no elements; the number of elements of A.

Questions people ask

Permutation or combination?

Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).

What is a graph in this sense?

Dots (vertices) joined by lines (edges) — not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.

Prova själv

Parts of this page are adapted from Levin, Discrete Mathematics: An Open Introduction (CC BY-SA 4.0). Condensed and re-explained here; errors are ours.

Mer information Combinatorics & Graph Theory

The counting principlesPigeonhole principle and inclusion–exclusionBinomial coefficients and Pascal's triangleRecurrences and generating functionsGraphs: vertices, edges, degreesPaths, cycles, trees, Euler and HamiltonColouring and planar graphs