Bipartite Graph Matching and Dance Arrangement: A Proof

Let v be a vertex of G with degree △(G). Since G is connected and bipartite, there exists a path P of odd length from v to any other vertex in G. Let w be a vertex with degree △(G) that is not adjacent to v. Since G is bipartite, every vertex on P is in the opposite part of the bipartition as v and w. Therefore, the vertices on P alternate between having degree △(G) and △(G)-1. Since P is of odd length, there must be a vertex on P with degree △(G)-1. Let x be such a vertex, and let y be the neighbor of x on P. Since y has degree △(G), there exists an edge between y and a vertex z with degree less than or equal to △(G)-1. We can repeat this argument with z instead of v to find a path P' of odd length from z to some vertex w' with degree △(G) that is not adjacent to z. By repeating this process, we can construct a path P, P', P'', ... of odd length that covers all vertices of degree △(G). Since each vertex on P, P', P'', ... has degree △(G)-1, we can find a matching covering all vertices of degree △(G) by matching the vertices on P, P', P'', ... with their neighbors that have degree △(G).

Let M be a matching of G of maximum size. Since G is bipartite, we can assume without loss of generality that the partite sets of G are X and Y, where |X|≥|Y|. Let S be the set of vertices in X that are not matched by M. Since every vertex in X has degree at most △(G), we have |S|≤|X|/△(G). Since every vertex in Y has degree at most △(G)-1, we have |M|≥|Y|-(|X|-|S|)≥|Y|-|X|/△(G). Therefore, we have |M|≥|E(G)|/|△(G)|.

We can represent the boys as vertices in one partite set of a bipartite graph, and the girls as vertices in the other partite set. We draw an edge between a boy and a girl if and only if the boy knows the girl. Then, every vertex has degree p, so the graph has minimum degree p. By Hall's theorem, there exists a matching covering all the girls. This means that each girl can dance with a boy she knows.