Bipartite Graph Matching Proofs and Dance Arrangement

1. Let 'v' be a vertex of degree △(G). Since G is bipartite, we can divide the vertices into two sets A and B such that 'v' is in A and all its neighbors are in B. Let S be the set of vertices in B that are not adjacent to 'v'. Since G is connected and bipartite, every vertex in S must have degree less than △(G). Therefore, we can apply Hall's theorem to the bipartite graph induced by A and S to find a matching that covers all vertices in A (which includes 'v') of degree △(G).

2. Let M be a maximum matching in G, and let S be the set of vertices of degree △(G). For each vertex 'v' in S, let N('v') be the set of neighbors of 'v' that are matched by M. Since each vertex in S has degree △(G), we have |N('v')| ≤ △(G) for all 'v' in S. Therefore, we have:

|E(G)| = 2|M| + |E(G)\M| ≤ 2|S| + △(G)(|V(G)| - 2|S|) = △(G)|V(G)| - (2△(G) - 2)|S| ≤ △(G)|V(G)| - 2|S|

where the second inequality follows from the fact that each edge in E(G)\M must be incident to a vertex in S, and the third inequality follows from the fact that |S| ≤ |V(G)|/2. Rearranging this inequality gives:

|M| ≥ (|E(G)| - △(G)|V(G)|)/2 + |S| ≥ (|E(G)| - △(G)|V(G)|)/2 + |V(G)|/(2△(G))

where the last inequality follows from the fact that |S| ≤ |V(G)|/(2△(G)). Therefore, we have a matching of size at least |E(G)|/△(G).

3. We can model this problem with a bipartite graph G, where the left side corresponds to the boys and the right side corresponds to the girls, and there is an edge between a boy and a girl if the boy knows the girl. Each vertex has degree 'p', so △(G) = 'p'. By part 1), we can find a matching covering all the vertices of degree 'p' on the right side. Since each girl is matched with a boy she knows, we can arrange them to dance with each other. We can then remove these matched vertices and repeat the process until all the girls have been matched. This gives an arrangement where every girl can dance with a boy she knows.