A tournament is a directed graph where between every two distinct vertices u and v, there is either an edge from u to v or an edge from v to u, but not both. Prove that every tournament has a Hamiltonian tour. (Hint: use induction on |V |, and show that the last element can be inserted somewhere on a tour that spans the first n - 1. )