Bipartite Graph Matching and Dancing Arrangements

Let v be a vertex of degree △(G). Since G is connected, there exists a path of length at least △(G) between v and any other vertex in G. Let P be a longest path starting at v, and let w be the endpoint of P. Since G is bipartite, v and w must be in different partite sets, say A and B respectively. Let N(w) be the set of neighbors of w in A. Since G is bipartite, every neighbor of w must be in A. Moreover, every vertex in A must have degree at most △(G)-1, since otherwise we could extend the path P. Therefore, |N(w)|=△(G). Now we can apply Hall's theorem to the bipartite graph induced by A and N(w), which shows that there exists a matching M covering all vertices of N(w). This matching also covers w, since w is adjacent to all vertices in N(w). Now we can remove all vertices covered by M, and repeat the argument with the remaining graph. Since G is finite, this process must terminate with a matching covering all vertices of degree △(G).

Let M be the matching constructed in part 1. Since every vertex of degree △(G) is covered by M, we have |M|=|V(△(G))|/2, where V(△(G)) is the set of vertices of degree △(G). Moreover, every vertex in G has degree at most △(G), so |E(G)|≤△(G)|V(G)|/2. Combining these inequalities, we get |M|≥|E(G)|/△(G).

We can represent the boys and girls as vertices in a bipartite graph G, where a boy is adjacent to a girl if and only if he knows her. Then every vertex in G has degree p, so △(G)=p. By part 1, there exists a matching covering all boys who know p girls. Let M be this matching, and let B be the set of boys covered by M. Since every boy in B knows p girls, there are pn edges between B and the set of girls they know. Moreover, every girl in this set has degree at least p, so there exists a matching covering all these girls. Combining this matching with M, we get a matching of size at least min{|B|,n}|p|/2, where |p| denotes the number of girls known by each boy. Since |B|=mp/n by the assumptions, we have |B|≥m/n, so the size of the matching is at least mp/2n^2. This means that we can pair up the girls and boys in the matching, and each girl will dance with a boy she knows. If there are any leftover boys or girls, we can repeat the argument with the remaining graph.