Bipartite Graph Matching and Dance Arrangement Proof

Let 'v' be a vertex of degree △(G). Since G is bipartite, we can partition the vertices into two disjoint sets 'A' and 'B', where 'v'∈A and every neighbor of 'v'∈B. Let 'U' be the set of all vertices in 'B' that are not adjacent to 'v', and let 'W' be the set of all vertices in 'A' that are adjacent to at least one vertex in 'U'. Since G is connected, there must be at least one vertex in 'W' that is adjacent to 'v'. Let 'u' be such a vertex. Then we can match 'u' with 'v', and remove 'u' and 'v' from the graph. Since G is bipartite, the resulting graph is still bipartite, and every vertex in the new graph has degree at most △(G)-1. We can repeat this process until there are no vertices of degree △(G) left. Since G is connected, every vertex has degree at least 1, so this process will cover all vertices.

Let 'M' be a maximum matching in G, and let 'S' be the set of vertices that are covered by 'M'. We will show that |M|≥|E(G)|/|S|. Let 'v' be a vertex in 'S', and let 'N(v)' be the set of neighbors of 'v'. Since G is bipartite, every vertex in 'N(v)' is in the other partite set, and therefore, not in 'S'. Since G is connected, we can find a path from 'v' to a vertex 'u'∈N(v). We can then alternate edges in 'M' and the path, starting with an edge in 'M', until we reach a vertex 'w'∈N(v) that is covered by 'M'. Since 'w' is covered by 'M', it must have a neighbor 'x' that is not covered by 'M'. Then we can extend our matching by adding the edges ('u','w') and ('v','x'), which covers two more vertices in 'S'. We can repeat this process until all vertices in 'S' are covered. Therefore, |M|≥|E(G)|/|S|.

Let G be the bipartite graph with boys on one side and girls on the other, and an edge between a boy and a girl if they know each other. Let △(G)='p', and let 'S' be the set of girls. Then every girl has 'p' neighbors in the boy set, so |S|≤m/p. Let 'M' be a maximum matching in G, and let 'T' be the set of boys that are matched in 'M'. Then every boy in 'T' is matched with a distinct girl in 'S', so |T|=|S|. By Hall's theorem, there exists a matching that covers all vertices in 'S', which means that every girl can dance with a boy she knows.