A tournament graph is a directed graph that has all edges uv, except that we either have the edge u v or v u (note that the number of edges is ). Indeed its as if we have n teams, and every pair of two teams plays one basketball game. If u lost to v, the tournament will have the edge u v. Clearly what we get is a tournament graph. Show that every tournament graph contains am Hamiltonian path. (Hint: Induction will make the answer simple). Give an algorithm that finds an Hamiltonian path in a tournament.

Please write time complexity.