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 NOTES ON MATCHING 3 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 necessary 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 marriage condition If we look at the set of boys B1 B2 B3 we see that they collectively like the same two girls This set …