Bipartite Graph Matching and Dance Arrangement Proof

Since G is bipartite, we can partition its vertices into two disjoint sets A and B such that every edge of G connects a vertex in A to a vertex in B. Therefore, △(G) is the maximum degree of vertices in either set A or set B. Without loss of generality, assume △(G) is the maximum degree of vertices in set A. Since G is connected, there exists a vertex v in set B that is adjacent to a vertex u in set A. Since G is bipartite, all the neighbors of u are in set B. If u has degree △(G), then v has at least one neighbor in set A. By repeating this argument, we can construct a matching of size △(G) that covers all the vertices of degree △(G) in set A.

Let M be a maximum matching in G. Since G is bipartite, every vertex in G is either in M or is adjacent to a vertex in M. Therefore, the number of vertices in G that are not covered by M is at most △(G). Since G is connected, there exists a vertex v in G that is adjacent to a vertex in M. Without loss of generality, assume v is in set A and its neighbor in M is in set B. Since G is bipartite, all the neighbors of v in set B are not in M. Therefore, the degree of v is at most △(G). By repeating this argument for all the vertices in set A, we can construct a matching that covers all the vertices of degree △(G) in set A and has size at least |E(G)|/△(G).

We can model this problem as a bipartite graph G with m vertices on one side representing the boys, n vertices on the other side representing the girls, and an edge between a boy vertex and a girl vertex if and only if the boy knows the girl. Since each boy knows p girls and each girl knows p boys, the degree of every vertex in G is p. By the Handshaking Lemma, m×p=n×p, so m=n. Therefore, G is a regular bipartite graph and has a perfect matching, which corresponds to an arrangement where every girl can dance with a boy she knows.