Group of kids forms bipartite graph
Source: 2023 Junior Macedonian Mathematical Olympiad P1
June 10, 2023
graph theorycombinatorics
Problem Statement
In a group of kids there are boys and girls. Every girl is a friend with exactly boys. Friendship is a symmetric relation: if A is a friend of B, then B is also a friend of A. Prove that it is not possible that all boys have the same number of girl friends. Proposed by the JMMO Problem Selection Committee