The 24/7 party of 25 elves
Source: Germany 2024, Problem 3
June 14, 2024
combinatoricscombinatorics proposedgraph theoryDirected graphs
Problem Statement
At a party, elves give each other presents. No elf gives a present to herself. Each elf gives a present to at least one other elf, but no elf gives a present to all other elves.
Show that it is possible to choose a group of three elves including at least two elves who give a present to exactly one of the other two elves in the group.