Every popular person is the best friend of a popular person?
Source: 2012 European Girls’ Mathematical Olympiad P6
April 13, 2012
combinatoricsEGMOEGMO 2012graph theory
Problem Statement
There are infinitely many people registered on the social network Mugbook. Some pairs of (different) users are registered as friends, but each person has only finitely many friends. Every user has at least one friend. (Friendship is symmetric; that is, if is a friend of , then is a friend of .)
Each person is required to designate one of their friends as their best friend. If designates as her best friend, then (unfortunately) it does not follow that necessarily designates as her best friend. Someone designated as a best friend is called a -best friend. More generally, if is a positive integer, then a user is an -best friend provided that they have been designated the best friend of someone who is an -best friend. Someone who is a -best friend for every positive integer is called popular.
(a) Prove that every popular person is the best friend of a popular person.
(b) Show that if people can have infinitely many friends, then it is possible that a popular person is not the best friend of a popular person.Romania (Dan Schwarz)