Problem

Source: Korea National Olympiad P3

Tags: combinatorics, graph



There are n boys and m girls at Daehan Mathematical High School. Let $d(B)$ a number of girls who know Boy $B$ each other, and let $d(G)$ a number of boys who know Girl $G$ each other. Each girl knows at least one boy each other. Prove that there exist Boy $B$ and Girl $G$ who knows each other in condition that $\frac{d(B)}{d(G)}\ge\frac{m}{n}$.