# Chess tournament, graph

Problem. In chess tournament each player, from all $n$ players, played one game with every another player. Prove that it is possible to number all players with numbers from $1$ to $n$ in such way that every player has unique number and none of them lost the game against player with number greater by $1$.

My first association was that this tournament can be represented by directed clique and for example edge $\langle a,b \rangle$ means that player with number $a$ won the game against player with number $b$. Then what I need to prove is that vertices in every directed clique with $n$ vertices can be numbered in such way that there in no edge $\langle i+1, \ i \rangle$ for all $i=1,2,...,n-1$.

But it seems very hard, I don't know how to approach.

Or maybe it isn't the problem from graph theory, I don't know.

-
I'm not sure that I understand the problem. What about a 3 players tournament where $A$ beats $B$, $B$ beats $C$ and $C$ beats $A$? – Andrea Mori Aug 29 '12 at 9:44
@AndreaMori Then any cyclic numbering would do, e.g. $A=1$, $B=2$, $C=3$. Then $1$ didn't loose against $2$ and $2$ didn't loose against $3$. – Simon Markett Aug 29 '12 at 9:55
@SimonMarkett : so the text should be interpreted "each player didn't lose a game with at least one higher numbered opponent"? Reading it, my interpretation was "...didn't lose with all higher numbered opponents", for which my 3-way tournament is an obvious counterexample. – Andrea Mori Aug 29 '12 at 10:01
Neither nore: No player lost the game against the player with number exactly $1$ higher. – Simon Markett Aug 29 '12 at 10:03
Well, looks like I really misunderstood the problem :) – Andrea Mori Aug 29 '12 at 10:16

So let's assume we have found a numbering for $n$ players and along comes the $n+1^{st}$ player and plays against every other player.
If he looses against the $n^{th}$ player, we give him the number $n+1$. If he wins against the $n^{th}$ player but also against the $1^{st}$ player, we give hm the number $1$ and move everybody else one up.
So assume he wins against the $n^{th}$ player and looses against the $1^{st}$ player. Then there is a number $k$ such that he wins against player $k$ and looses against player $k-1$. Then we give him the number $k$ and move everybody with a number $>k$ one up.