# Prove the following "connected" problem

There are $n$ people in the room, some know each other and some don't. If $i$ knows $j$, then $j$ knows $i$. Suppose that for every four different people there exists one who knows the remaining three. A person who knows all the rest is called "connected".

a. Prove that there exists a "connected" person

b. Prove that at least $n-3$ people are "connected"

HINT for (a): Suppose that there is no connected person. Then for each person $p$ there is a person $q$ whom $p$ does not know. Pick a person $p$, and let $q$ be someone whom $p$ does not know. Pick a third person, $r$, different from both $p$ and $q$.
• If $r$ knows both $p$ and $q$, then there must be a fourth person, $s$, whom $r$ does not know. Is the set $\{p,q,r,s\}$ possible under the hypotheses of the problem?
• Suppose that $r$ does not know $p$, and let $s$ be any fourth person different from $p,q$, and $r$. Then $s$ must know each of $p,q$, and $r$; why? Still, there is some person $t$ whom $s$ does not know; consider the set $\{p,q,s,t\}$.
HINT for (b): If the assertion is false, then there are at least $4$ people who are not connected. That’s enough unconnected people for you to carry out a slight modification of the argument sketched above for (a).