If $A$ designates $B$ as her best friend, we denote $A \to B$. Lemma: If $A$ is an $n$-best friend, then for any positive integer $k \leqslant n$, $A$ is an $k$-best friend. Proof: $n = 1$ is obviously. Suppose $n \geqslant 2$, and the lemma is right for any positive integer $ < n$, because $A$ is an $n$-best friend, there exit an $(n - 1)$-best friend $X$, $X \to A$. So $A$ is a $1$-best friend, for any integer $2 \leqslant k \leqslant n$, $1 \leqslant k - 1 \leqslant n - 1$, so $X$ is an $k - 1$-best friend, hence $A$ is an $k$-best friend. Definition: If $A$ is an $n$-best friend, but is not an $n + 1$-best friend, we denote $P(A) = k$. If $A$ is a popular person, we denote $P(A) = + \infty $. (a)Proof: For any popular person $A$, we denot the set of her friends is $F = \left\{ {{X_1},{X_2},...,{X_m}} \right\}$, and $G = \left\{ {{X_i}\left| {{X_i} \to A} \right.} \right\}$, if there not exit any popular person in $G$, we can take $M = \max \left\{ {P({X_i})\left| {{X_i} \in G} \right.} \right\}$, then $P(A) = M + 1$, $A$ is not a popular person, contradiction. (b)Proof: If people can have infinitely many friends, denote all users are $1,2,...,n,...$. $1 \to 10 \to {10^2} \to {10^3} \to ...$; For any ${10^i} < j < \left( {{{10}^{i + 1}} - 1} \right)$, $j \to j + 1$; For any positive $i$, $\left( {{{10}^{i}} - 1} \right) \to 1$. It is easy to see $1,10,{10^2},...$ are all popular persons, and $1$ is not the best friend of any popular person.

this is an obvious application of König's infinity lemma for more information see this: http://en.wikipedia.org/wiki/K%C3%B6nig%27s_lemma

First of all, rewrite this problem into the format of a directed graph, which is induced from a graph with infinitely many vertices with each vertex having finite degree. The main idea behind this problem that we have to face is this. What is the difference between (a) and (b)? They seem almost identical. We suspect that the difference between these two cases will determine the true result and the false result. After significant experimentation, we find that the only real difference between them is that in one case, The induced directed graph must have each vertex have a non infinite indegree This immediately cracks the problem. For (a), any popular person has only finite maximal paths leading into it, so the conditions of popularity dictate that one of these paths is infinite, which finishes. For (b), take the graph with $p_k^k \rightarrow p_k^{k-1} \cdots\rightarrow p_k$, where $p_k$ is the $k$'th prime number. Observe that none of these intersect and they trivially satisfy the condition, so we are done.

Main Claim: If a person is a $n$-best friend, then he is also a $k$-best friend for all positive integers $k\leq n$. We will show this by induction. This is clearly true for $n=1,2$. Now, suppose this is true for $n$ and we will try to show it for $n+1$. Now, suppose that person $P$ is a $n+1$-best friend. Then, he is the best friend of some $n$-best friend. However, by our inductive hypothesis, the $n$-best friend is a $k$-best friend for all $1\leq k\leq n$. Hence, $P$ is a $k$-best friend for all $2\leq k\leq n+1$. Clearly, he is also a 1-best friend, which shows the claim by induction. Consider a person $P$ that is not the best friend of any popular person. Then, since each person only has finitely many friends, there can only be a finite number of people, say $m$ that have $P$ as their best friend. Label those people $1$ through $m$, and let $h_i$ be the largest positive integer $k$ such that person $i$ is a $k$-best friend. Note that by our claim above, $h_i$ exists for any non-popular person since they can only be $k$-best friends up to a certain point and then stop. Then, clearly, $P$ is not a $\max(h_1,h_2\cdots ,h_m)+2$-best friend, so $P$ is not popular, which solves part (a). For (b), let one person be $P$. For every positive integer $n$, have a chain of $n$ people such that the first one's best friend is the second, the second one's best friend is the third, and so on until the last one's best friend is $P$. Then, have $P$ feed into an infinite chain $P_1,P_2,P_3\cdots$. None of the people that have $P$ as their best friend are popular, but $P$ is popular since there is a chain of every possible length feeding into $P$.

My solution is same as above

Solution from Twitch Solves ISL: First note the following statement is true by induction: Claim: Someone who is an $n$-best friend is also a $k$-best friend for all $1 \le k < n$. Proof. Induction on $(k,n)$. $\blacksquare$ 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.