NOTES ON MATCHING Jonathan Hirata 1. Introduction and Definitions This paper assumes basic knowledge of definitions and concepts as they pertain to graph theory. With that in mind, let’s begin with the main topic of these notes: matching. For now we will start with general definitions of matching. Later we will look at matching in bipartite graphs then Hall’s Marriage Theorem. 1.1. General Definitions. Definition 1.1. A matching of graph G is a subgraph of G such that every edge shares no vertex with any other edge. That is, each vertex in matching M has degree one. Definition 1.2. The size of a matching is the number of edges in that matching. Figure 1 Consider the graph in Figure 1. Denote the edge that connects vertices i and j as (i, j). Note that {(3, 8)} is a matching. Obviously we can get more. The pairs {(3, 8), (4, 7)} also make a matching. That is a matching of size two. Can we get a matching of size three? Yup, it’s {(2, 3), (4, 8), (5, 7)}. Can we do even better? Well, a matching of size four means that every vertex is paired, but vertices 1 & 2 must both be paired with vertex 3. So no, three is the best we can do. We call it a maximum matching. Definition 1.3. A matching is maximum when it has the largest possible size. Note that for a given graph G, there may be several maximum matchings. Definition 1.4. The matching number of a graph is the size of a maximum matching of that graph. Thus the matching number of the graph in Figure 1 is three. Definition 1.5. A matching of a graph G is complete if it contains all of G’s vertices. Sometimes this is also called a perfect matching. Thus no complete matching exists for Figure 1.� 2 NOTES ON MATCHING 1.2. Matching in Bipartite Graphs. Let’s begin with a recap of what a bipartite graph is: Definition 1.6. A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that no edge connects two vertices of the same set. It is common to use the terms left and right to describe the two sets of vertices. A balanced bipartite graph is one that has an equal number of left and right vertices. Definition 1.7. Consider a subset S ≤ L of left vertices of bipartite graph G. Let n be the number of right vertices the set S is connected to. Then the deficiency D of set S is defined as: |S| − n if positive D(S) = 0 otherwise Define the left deficiency DL of a bipartite graph as the maximum such D(S) taken from all possible subsets S. Right deficiency DR is similarly defined. As an example, let’s consider the complete bipartite graph K3,2. Recall that Km,n stands for a complete bipartite graph with m left vertices and n right vertices. Figure 2. K3,2 If we consider the subset S = {L1, L2}, we see that the deficiency of this subset is zero, as the number of neighbors of S is at least the size of S. But if we consider the subset S = {L1, L2, L3}, we find a deficiency of one, as these three left vertices connect to only two right vertices. Since there exists no larger deficiency, the left deficiency of K3,2 has a value of one. Now let’s look at the right side of our graph. Consider the subset S = {R1}. Since this vertex connects to 3 left vertices, this subset has a deficiency of zero. In fact it is easy to see that the right deficiency of our graph is also zero. With these concepts in place, we will now offer a proposition, to be proven later. Proposition 1.8. The matching number of a bipartite graph G is equal to |L| − DL(G), where L is the set of left vertices. Likewise the matching number is also equal to |R| − DR(G), where R is the set of right vertices. Referring back to Figure 2, we see that |L| − DL(G) = |R| − DR(G) = 2. And clearly a matching of size 2 is the maximum matching we are going to find. We will now switch gears slightly and focus on a particular subcase of the above proposition. We will now focus on the case where we can find a complete matching. The result we are after is known as Hall’s Marriage Theorem.3 NOTES ON MATCHING 1.3. Hall’s Marriage Theorem. Philip Hall in 1935 gave us the condition for when a complete matching is possible in a bipartite graph. An easy was to visualize this is to consider the following situation: Suppose we are pairing up N boys and N girls (if they were not both N then clearly there is no way for a matching of our bipartite graph to be complete). Now each girl comes up with a list of acceptable mates that she likes, some subset of the N boys. Since these boys are of the gentlemanly type, none of them will reject a proposal if given to them. This situation can be represented by a bipartite graph, where an edge represents the event that a specific girl likes a specific guy. One such possible arrangement is given in Figure 3. Figure 3 We can now state Hall’s marriage condition: Definition 1.9. Hall’s marriage condition holds when every subset of r girls likes at least r boys. This is exactly the same as saying Hall’s marriage condition holds when DL(G) = 0 (or DR(G) = 0) for a balanced bipartite graph G. An equivalent condition can be created by interchanging ‘boy’ and ‘girl’ in the definition above. Also note that the marriage condition only applies to the case where we have an equal number of boys and girls, i.e. when we have a balanced bipartite graph. Can you see how you would relate this condition to a bipartite graph? Here is the main theorem of this section. Theorem 1.10 (Hall’s Marriage Theorem). Hall’s marriage condition is both nec-essary and sufficient for the existence of a complete match in a bipartite graph. That is to say, iff Hall’s marriage condition holds for a bipartite graph, then a complete matching exists for that graph. Looking at Figure 3 we can see that this graph does not meet the marriage condition. If we take the set of girls {G3, G4}, they are both paired with only one boy, thus they have a deficiency of one. This violates the marriage condition. Here it is easy to see that no complete matching exists because of this: only at most one of {G3, G4} could get married, the other one won’t be. If we look at the marriage condition from the boy’s side, we also see a violation of the