Question 69
Infinitely many people are registered users of the social network Mutrăbook. Some pairs of distinct users are friends, but each person has only finitely many friends. Each user has at least one friend. Friendship is symmetric: if $A$ is a friend of $B$, then $B$ is a friend of $A$.
Each person must designate one friend as their best friend. If $A$ designates $B$, it does not necessarily follow, unfortunately, that $B$ designates $A$. Someone designated as a best friend is called a 1-best friend. In general, for a positive integer $n\gt1$, a user is an $n$-best friend if designated by someone who is an $(n-1)$-best friend. A person who is a $k$-best friend for every positive integer $k$ is called popular.
a. Prove that each popular person is the best friend of at least one other popular person.
b. Prove that if people were allowed infinitely many friends, a popular person could be the best friend of no other popular person.
Each person must designate one friend as their best friend. If $A$ designates $B$, it does not necessarily follow, unfortunately, that $B$ designates $A$. Someone designated as a best friend is called a 1-best friend. In general, for a positive integer $n\gt1$, a user is an $n$-best friend if designated by someone who is an $(n-1)$-best friend. A person who is a $k$-best friend for every positive integer $k$ is called popular.
a. Prove that each popular person is the best friend of at least one other popular person.
b. Prove that if people were allowed infinitely many friends, a popular person could be the best friend of no other popular person.