Matching in Bipartite Graphs: Existence and Size Bounds

Let S be the set of all vertices with degree △(G). Since G is bipartite, we can partition V(G) into two sets, A and B, such that each edge of G has one endpoint in A and one endpoint in B. Without loss of generality, assume that △(G) is the maximum degree of vertices in A. For every vertex u in S, let N(u) be the set of neighbors of u in B. Since G is connected, we have |N(u)|≥1 for every u in S. By Hall's theorem, there exists a matching M that covers all vertices in S.

Let S and N(S) be the sets of vertices with degree △(G) and their neighbors, respectively. Then, we have |S|=△(G)k and |N(S)|=△(G)k', where k and k' are the number of vertices in A and B, respectively. Since G is bipartite, we have |E(G)|=k'△(G). By the pigeonhole principle, there exists a vertex u in S such that |N(u)|≥k'/k. Let M be the set of edges incident to u and the vertices in N(u). Then, we have |M|≥k'/k=|N(u)|/|S|. Since every vertex in S is incident to at most △(G) edges, we have |M|≥|N(S)|/△(G)≥|E(G)|/△(G)^2. Thus, we have |M|≥|E(G)|/|△(G)|.

We can represent the boys by vertices in set A and the girls by vertices in set B. Since each boy knows exactly p girls and each girl knows exactly p boys, we have that the degree of every vertex in A and B is p. We will show that there exists a perfect matching between A and B, which implies that every girl can dance with a boy she knows. Let S be a subset of A, and let N(S) be the set of neighbors of S in B. Then, we have |S|=p|N(S)| and |N(S)|=p|S|. By Hall's theorem, there exists a matching that covers S. Since S is arbitrary, we can apply Hall's theorem again to show that there exists a perfect matching between A and B.