Bipartite Graph Matching Proofs and Dance Arrangement

1. Let v be a vertex of degree △(G). By Hall's Marriage Theorem, there exists a matching covering every neighbor of v. Removing these edges, we are left with a bipartite graph G' where every vertex in the partite set containing v has degree at most △(G)-1. By induction on the number of vertices, G' has a matching covering all vertices of degree △(G)-1. Adding back the edges we removed, we obtain a matching covering all vertices of degree △(G).

2. Let M be a maximum matching of G, and let S be the set of vertices not covered by M. Consider any vertex v in S. Since G is bipartite, v has a neighbor u in M. By the maximality of M, u must have another neighbor w not in M. Since G is bipartite, w is not adjacent to any vertex in S. Therefore, we can construct a new matching M' by replacing the edge uw in M with the edge vw. This increases the size of the matching by 1, and also covers v. Repeating this process for all vertices in S, we obtain a matching covering all vertices of degree △(G). The size of this matching is at least |M|+|S|/2, since each edge covers two vertices.

3. Let G be the bipartite graph with boys on one side and girls on the other, and edges representing who each boy knows. Note that G is connected and bipartite, so △(G) = p. By part 2), G has a matching of size at least m. Let M be such a matching. For each girl, let M(g) be the set of boys she matches with in M. Since each girl knows exactly p boys, we have |M(g)| = p for all girls g.

We can now construct an arrangement as follows: for each girl g, let her dance with any boy in M(g). Since |M(g)| = p, this is always possible. Moreover, since each boy is matched with at most one girl, every girl gets to dance with a boy she knows.