Here is a combinatorics problem having to do with graph-theory
Ten players participate at a chess tournament. Eleven games have already been played. Prove that there is a player who has played at least 3 games.
Here is a combinatorics problem having to do with graph-theory
Ten players participate at a chess tournament. Eleven games have already been played. Prove that there is a player who has played at least 3 games.
Say player $i$ has played $r_i$ games. Since $11$ games have been played $r_1+r_2+\ldots +r_{10}=22.$ If we suppose that each player has played at most 2 games then $r_1+r_2+\ldots +r_{10}\leq 20$ giving us a contradiction.
Not exacly Graph Theory, more Pigeonhole Principle. Every time a player plays a game, she makes an X on the blackboard. Since $11$ games have been played, and each game involves $2$ people, there are $22$ X on the blackboard. So one player must have made $3$ or more X. This is because if all players had made $2$ or fewer X, there would be at most $20$ X on the board.
Or else think in terms of money. Every time a player plays, she puts $1$ dollar into the beer fund. Since $11$ games have been played, there are $22$ dollars in the beer fund. So one player at least must have put in $3$ dollars or more, that is, played $3$ or more games.