Graph Theory(trees) problem? I am practicing for my Discrete Math final and came across this question on trees in my textbook(Rosen). 
Suppose 1000 people enter a chess tournament. Use a rooted tree model of the tournament to determine how many games must be played to determine a champion, if a player is eliminated after one loss and games are played until only one entrant has not lost. (Assume there are no
ties.)
I am not exactly sure how to even get started with something like this using trees(although I have read the section on trees). The answer and an explanation would be nice since I don't have the solutions manual.
 A: As Brian M. Scott mentioned, the correct answer is that 999 games must be played.
To get this solution using trees, let the root represent the winner and let the children of each node be the players who played a particular game, and the parent of a node be the winner of the game that they played. This is a binary tree, and so it is not too hard to see that to accommodate 1000 starting players, you will need 10 "generations" (this is where my terminology starts to get fuzzy) in addition to the root.
The remaining 24 slots can be filled with dummy players who always lose ("byes") and the most efficient method is to eliminate all of them at once,  so there will be 24 players who move to the second level uncontested.
At this point you can simply count them (not by hand, of course! unless you are trying to waste time). Keep in mind that because of the byes, the first layer is a bit special. If you do all the counting correctly, you will get 999 games.
A: To put it in purely graph theoretic terms, we can model this situation in terms of a $2$ - ary tree or a binary tree. Let the tree have a total of $ n $ vertices, $ i $ internal vertices (all the vertices except the leaves) and $ l $ leaves. 
Now, since there are no constraints on how many games each person has to play, we can do the following. Construct the tree from the leaves.
There are $ l $ leaves that represent the players. Thus, $ l = 1000 $. Every time we go up a level, we eliminate one player with $ 1 $ match. If you observe carefully, the number of matches equals the number of internal nodes $ i$. 
Now, in an $ m $ - ary tree, if we are given the number of leaves $ l$, the number of internal nodes are found by the following formula:
$$ \large i = \dfrac{l - 1}{m - 1} = \dfrac{1000 - 1}{2 - 1} = \boxed{999} $$
since in our case $ m = 2 $ and $ l = 1000$.
