Problem: 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.
\begin{enumerate}
  \ii[(a)] Prove that every popular person is the best friend of a popular person.
  \ii[(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.
\end{enumerate}

Solution: First note the following statement is true by induction:
\begin{claim*}
  Someone who is an $n$-best friend is also a $k$-best friend for all $1 \le k < n$.
\end{claim*}
\begin{proof}
  Induction on $(k,n)$.
\end{proof}

For part (a), suppose Dan is a popular person.
Let the friends of Dan be $P_1$, $P_2$, \dots, $P_m$.
For each $n$, one of the $P_i$'s must be an $n$-best friend.
By pigeonhole, one of the $P_i$'s is an $n$-best friend for infinitely many $n \ge 1$.
Hence be the claim above they are popular too.

For part (b), consider a social graph defined by having Dan ($D$)
and the following chains of best friends:
\begin{align*}
  D &\longleftarrow P_{11} \\
  D &\longleftarrow P_{21} \longleftarrow P_{22} \\
  D &\longleftarrow P_{31} \longleftarrow P_{32} \longleftarrow P_{33} \\
  D &\longleftarrow P_{41} \longleftarrow P_{42} \longleftarrow P_{43} \longleftarrow P_{44} \\
  &\vdotswithin{\longleftarrow}
\end{align*}
Then Dan is the only popular person in the entire network.
This gives the construction promised.