MATH 61 Midterm: MATH 61 Exam 8
Document Summary
Final review solutions: for n = 1 a tournament is a single vertex which is a hamiltonian path. For n = 2 a tournament is of the form a b which again is a hamiltonian path. Suppose that we know it is true up through k vertices. Let us consider the case of k + 1 ver- tices. Now let us consider the vertex k + 1. If the arc between k + 1 and. 1 is (k + 1) 1 then we can modify the path as (k + 1) 1 k and we are done. Similarly, if the arc between k + 1 and k is k (k + 1) then we can modify the path as 1 k (k + 1) and we are done. 1 k and (k + 1) k, then there is some smallest. 1 < i k so that (k + 1) i, note that we must have (i 1) (k + 1).
