Ten people in a room 
There are ten people in a room:
Person $1$ knows $9$ people. Person $2$
  knows $8$ people. etc. Person $9$ knows $1$
  person.
How many people does person $10$ know?

What is the answer and what is the principle behind this question?
 A: You can think of this as a problem in graph theory.  You have a graph $G$ on ten vertices (the ten people in the room ${ 1, 2, 3, ... 10 }$) where two people are connected by an edge if and only if they know each other.  The degree or valence of a vertex $v \in G$, denoted $d_v$, is the number of edges connected to it (the number of people someone knows).  You are given that $d_1 = 9, d_2 = 8, ... d_9 = 1$ and you want to know $d_{10}$ (so the problem gives you information here: it tells you that $d_{10}$ is uniquely determined by these conditions).
Here's one way to solve it, in steps.


*

*Person $1$ must know everyone else; that is, he must be connected to all of the other vertices (including person $10$).  In particular, he must be the only person that person $9$ knows.  

*Person $2$ must know everyone else except one person, and since person $9$ only knows person $1$, person $2$ must know everyone else except person $9$ (including person $10$).  In particular, he must be the only other person that person $8$ knows.

*Person $3$ must know everyone else except two people, and since persons $8$ and $9$ have all their friends accounted for, person $3$ must know everyone else except persons $8$ and $9$ (including person $10$).  In particular, he must be the only other person that person $7$ knows.

*... and so forth.  By induction we conclude that person $10$ knows persons $1, 2, 3, 4, 5$ but not persons $6, 7, 8, 9$.  So $d_{10} = 5$.

