Lecture 2 A perfect matching in a bipartite graph with two sets of equal size is a collection of edges such that every vertex is contained in exactly one of them. Hall's(marriage)theorem is a necessary and sufficient condition which allows one to decide if a given bipartite graph contains a matching.Suppose that the two parts of the bipartite graph G are A and B.Then Hall's theorem says that if,for every subset U of A,there are at least vertices in B with neighbours in U then G contains a perfect matching The condition is clearly necessary.To prove that it is sufficient we use the following notation. For any subset X of a graph G,let NG(X)be the set of neighbours of X,that is,the set of vertices with a neighbour in X. Theorem 1 (Hall's theorem)Let G be a bipartite graph with parts A and B of equal size.If,for every U C A,NG(U)>U then G contains a perfect matching. Proof Let Al =BI=n.We will prove the theorem by induction on n.Clearly,the result is true for n=1.We therefore assume that it is true for n-1 and prove it for n. If N(U)1 for every non-empty proper sabset U of A,pick an edge ofGand consider the e graph G=G-{a,b).Then every non-empty set U C}satisfies INc(U)I≥lNc(U)I-1≥IUL. Therefore,there is a perfect matching between}and B\).Adding the edge from a to b gives the full matching. proper subset Uof A for which NU) eN.y indnetion since Hail's condition holds for evry subset of V.there sa inatching re is some nor empty p between U and V.But Hall's condition also holds between A\U and B\V.If this weren't the case, there would be some W in AlU with fewer than WI neighbours in B\V.Then WUU would be n B,contradicting our assumption. Therefore. thrhn t and BV.Putting the to tch o the proof. ■ A Hamiltonian cycle in a graph G is a cycle which visits every vertex exactly once and returns to its starting vertex.Dirac's theorem says that if the minimum degree 6(G)of a graph G is such that 6(G)2n/2 then G contains a Hamiltonian cycle.This is sharp since,if one takes a complete bipartite graph with one part of size(and the other the complement of this),then it canot contain a Hamiltonian cycle.This is simply because one must pass back and forth between the two sets. Theorem 2(Dirac's theorem)If a graph G satisfies 6(G)>,then it contains a Hamiltonian cycle Proof First,note that G is connected.If it weren't,the smallest component would have size at most n/2 and no vertex in this component could have degree n/2 or more. Let P=zoz1...k be a longest path in G.Since it can't be extended,every neighbour of ro and rk must be contained in P.Since (G)2n/2,we see that roi+is an edge for at least n/2 values of i 1 Lecture 2 A perfect matching in a bipartite graph with two sets of equal size is a collection of edges such that every vertex is contained in exactly one of them. Hall’s (marriage) theorem is a necessary and sufficient condition which allows one to decide if a given bipartite graph contains a matching. Suppose that the two parts of the bipartite graph G are A and B. Then Hall’s theorem says that if, for every subset U of A, there are at least |U| vertices in B with neighbours in U then G contains a perfect matching. The condition is clearly necessary. To prove that it is sufficient we use the following notation. For any subset X of a graph G, let NG(X) be the set of neighbours of X, that is, the set of vertices with a neighbour in X. Theorem 1 (Hall’s theorem) Let G be a bipartite graph with parts A and B of equal size. If, for every U ⊂ A, |NG(U)| ≥ |U| then G contains a perfect matching. Proof Let |A| = |B| = n. We will prove the theorem by induction on n. Clearly, the result is true for n = 1. We therefore assume that it is true for n − 1 and prove it for n. If |NG(U)| ≥ |U| + 1 for every non-empty proper subset U of A, pick an edge {a, b} of G and consider the graph G0 = G − {a, b}. Then every non-empty set U ⊂ A\{a} satisfies |NG0(U)| ≥ |NG(U)| − 1 ≥ |U|. Therefore, there is a perfect matching between A\{a} and B\{b}. Adding the edge from a to b gives the full matching. Suppose, on the other hand, that there is some non-empty proper subset U of A for which |N(U)| = |U|. Let V = N(U). By induction, since Hall’s condition holds for every subset of U, there is a matching between U and V . But Hall’s condition also holds between A\U and B\V . If this weren’t the case, there would be some W in A\U with fewer than |W| neighbours in B\V . Then W ∪ U would be a subset of A with fewer than |W ∪ U| neighbours in B, contradicting our assumption. Therefore, there is a perfect matching between A\U and B\V . Putting the two matchings together completes the proof. ✷ A Hamiltonian cycle in a graph G is a cycle which visits every vertex exactly once and returns to its starting vertex. Dirac’s theorem says that if the minimum degree δ(G) of a graph G is such that δ(G) ≥ n/2 then G contains a Hamiltonian cycle. This is sharp since, if one takes a complete bipartite graph with one part of size d n 2 − 1e (and the other the complement of this), then it cannot contain a Hamiltonian cycle. This is simply because one must pass back and forth between the two sets. Theorem 2 (Dirac’s theorem) If a graph G satisfies δ(G) ≥ n 2 , then it contains a Hamiltonian cycle. Proof First, note that G is connected. If it weren’t, the smallest component would have size at most n/2 and no vertex in this component could have degree n/2 or more. Let P = x0x1 . . . xk be a longest path in G. Since it can’t be extended, every neighbour of x0 and xk must be contained in P. Since δ(G) ≥ n/2, we see that x0xi+1 is an edge for at least n/2 values of i 1