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 A is a friend of B, then B is a friend of A.)
Each person is required to designate one of their friends as their best friend. If A designates B as her best friend, then (unfortunately) it does not follow that B necessarily designates A as her best friend. Someone designated as a best friend is called a 1-best friend. More generally, if n>1 is a positive integer, then a user is an n-best friend provided that they have been designated the best friend of someone who is an (n−1)-best friend. Someone who is a k-best friend for every positive integer k 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) combinatoricsEGMOEGMO 2012graph theory