Bipartite Graph Matching and Dance Arrangement: Proofs and Applications

Since G is bipartite, let X and Y be the two color classes of G. Let S be the set of vertices in X with degree △(G) and let T be the set of vertices in Y with degree less than △(G). Then |S|=|T| since G is connected. By Hall's theorem, there exists a matching M from S to T, which covers all vertices in S. Since G is bipartite, this matching also covers all vertices in X with degree △(G).

Let M be a maximum matching of G. Then every vertex in G is in M or is adjacent to a vertex in M. Since every vertex in M has degree 1, there are at least |E(G)|/2 vertices in G that are not in M. Let V be the set of vertices in G with degree △(G). Then |V|≥|E(G)|/(2△(G)) since every vertex in V has degree at least △(G). By part 1), there exists a matching that covers all vertices in V. Therefore, the size of this matching is at least |V|/△(G)≥|E(G)|/(2△(G)△(G))=|E(G)|/|△(G)|.

We can represent the boys and girls as vertices in a bipartite graph G, where there is an edge between a boy and a girl if and only if they know each other. Then each vertex in G has degree p, so △(G)=p. Let S be the set of girls in G. Then every girl in S is adjacent to p boys, so |S|≤m/p. By Hall's theorem, there exists a matching M from S to the set of boys in G, which covers all vertices in S. Therefore, every girl in S can dance with a boy she knows.