In a group of n people ($n \geq 2$) at least two person knows each other. Assume that if two persons have a mutual friend, they know different number of people.
Prove that in this group there exist a person that knows only one person.
My approach is the following:
Let $G=(V,E)$ be a graph such that $|V(G)|=n$. Assume the contrary, that $deg(v)\geq 2$, for all $v \in V(G)$. At least two person knows each other so let $v,w \in V(G)$ be such that $(v,w) \in E(G)$. But, from the assumption $deg(v),deg(w)\neq 1$, so there is at least one person $s\in V(G)$ such that $v,w,s$ form a cycle. But then they all have a mutual friend, so all know different number of people.
But know I am stuck and don't know how to finish the argument.
Best Answer
Let $v$ be a vertex with the highest degree $k\geq 1$ in $G$. Let $v_1,\ldots, v_k$ be the vertices connected to $v$. Since $v_i$ and $v_j$ have a common neighbor, we have $\deg v_i \neq \deg v_j$ for all $i\neq j$. But $1 \leq \deg v_i \leq k$ for all $i$ and if they are all distinct, one must have $\deg v_i =1$ for some $i$.