Bipartite Graph Matching and Dance Arrangement Proof

1. Since G is bipartite, we can divide its vertices into two disjoint sets A and B such that all edges of G connect a vertex in A with a vertex in B. Let d be the degree of a vertex u in A with maximum degree. We will show that there exists a matching M that covers all vertices in A of degree d.

Suppose, for the sake of contradiction, that there is no matching in G that covers all vertices in A of degree d. Then, by Hall's theorem, there exists a set S of vertices in A such that the number of neighbors of S in B is less than |S|. Let T be the set of neighbors of S in B. Since G is connected, there exists a path from each vertex in S to each vertex in T. Let v be a vertex in T such that d(v) = △(G). Let w be a neighbor of v in S. Since w has degree less than △(G), there exists a neighbor u of w in B such that u is not adjacent to any other vertex in S. But then we can add the edge uw to the matching M, contradicting the assumption that there is no matching in G that covers all vertices in A of degree d. Therefore, such a matching M must exist.

2. Let M be a matching in G of maximum size. We will show that |M| ≥ |E(G)|/△(G). Let A and B be the two parts of G as before. Since G is bipartite, we have |E(G)| = |A||B|. Let S be the set of vertices in A that are not covered by M. Then, the number of neighbors of S in B is at least |S|△(G), since each vertex in S has degree at most △(G) and no two vertices in S are adjacent to the same vertex in B. Thus, the number of edges going from S to B is at least |S|△(G)/2, since each edge is counted twice. On the other hand, since M is a matching, each vertex in B is adjacent to at most one vertex in S, so the number of edges going from B to S is at most |S|. Therefore, we have

|E(G)| = |A||B| = |M| + |S| + |E(S,B)| ≤ |M| + |S| + |S|△(G)/2.

Solving for |M|, we get |M| ≥ |E(G)|/△(G).

3. Let G be the bipartite graph with boys on one side and girls on the other, where there is an edge between a boy and a girl if the boy knows the girl. Then, the degree of each vertex in G is p, so △(G) = p. By part 1), there exists a matching M that covers all girls who know p boys. We will show that this matching covers all girls.

Suppose, for the sake of contradiction, that there exists a girl v who is not covered by M. Then, v must know at most p-1 boys. Let S be the set of boys that v knows. Then, |S| ≤ p-1. Since each boy knows p girls, the number of girls that the boys in S know is at least |S|p. But then, by the pigeonhole principle, there must be a girl w who is known by two different boys in S. Let u and x be two such boys. Then, there are edges vw, uw, and xw in G. Since M covers all girls who know p boys, v must know at least one other boy y who is not in S. But then, there is an edge vy in G, which contradicts the assumption that v is not covered by M. Therefore, such a matching M must cover all girls, and the boys can dance with the girls they know.