Bipartite Graph Matching Proofs and Application to Dance Arrangement

1. Let S be the set of vertices of degree △(G), and let T be the set of vertices of degree less than △(G). Since G is bipartite, we can partition the vertices into these two sets. Let H be the subgraph induced by T. Then △(H)<△(G), so by induction, H has a matching covering all vertices of degree △(H). Now consider any vertex v in S. Since G is connected, there exists a path from v to some vertex w in T. Since the degree of w is less than △(G), there exists an unmatched neighbor x of w in H. We can then match v with x, and repeat this process until all vertices in S are matched. This gives a matching covering all vertices of degree △(G).

2. Let M be a maximum matching in G. Since G is bipartite, every vertex of degree △(G) is matched in M. Let S be the set of vertices of degree △(G) and let T be the set of vertices of degree less than △(G). Consider the subgraph H induced by T. Since every vertex in S is matched in M, we have |M|≤|S|. Also, every vertex in H has degree less than △(G), so by the handshake lemma, |E(H)|≤△(G)|T|. Combining these two inequalities, we have:

|E(G)|=|M|+|E(H)|≤|S|+△(G)|T|=△(G)(|S|+|T|)=△(G)|V(G)|

Dividing both sides by △(G), we get |M|≥|E(G)|/△(G).

3. Let G be the bipartite graph with boys on one side and girls on the other, and edges representing who knows whom. We can assume without loss of generality that m≤n, so that the boys are the smaller side of the bipartition. Let X be a set of m boys, and let Y be the set of girls that they know. We will show that there exists a perfect matching between X and Y, which implies that every girl can dance with a boy she knows.

Let H be the subgraph of G induced by X∪Y. Then every vertex in H has degree p, so by the handshake lemma, |E(H)|=p|X|. Also, since every boy knows exactly p girls, we have |Y|=mp. Now consider any subset S of X. The set of girls they know is a subset of Y, so has size at most p|S|. By Hall's theorem, there exists a matching between X and Y that covers every boy in X, which implies that every girl in Y is also matched. Therefore, there exists a perfect matching between X and Y, and every girl can dance with a boy she knows.