I am working on the below proof. I am still new to proves so I am wondering if you guys can answer the following questions:
1) Did I use the inductive hypothesis correctly here? (By the inductive hypothesis, we know that both From and To are smaller versions of the larger tournament so there is a Hamiltonian path in both From and To.)
1b) is there a better way to show that these subsets have a Hamiltonian path?
2) Does my proof flow logically and is it clear?
3) Is this proof correct?
Any tips and welcomed!! THANKS FOR YOUR ADVICE!
Graph to represent the outcome of a round-robin tournament, in which every player plays every other player. An edge goes from the victor of each match to the loser.
Definition 1. A tournament graph is a directed graph G = (V, E) without loops, in which for every two vertices u and v, exactly one of (u, v) or (v, u) are in E.
Definition 3. A Hamiltonian path through a graph is a path that visits each vertex exactly once. Note that a Hamiltonian path is not a cycle.
Prove using strong induction that every tournament graph has a Hamiltonian path.
For a graph with the number of vertices n = 1 then there is a Hamiltonian path of that single vertex. When n > 1, we can consider a graph with n + 1 vertices where the vertices 1…..n contain a Hamiltonian path. An arbitrary vertex v can be chosen from this graph in which, by the definition of a tournament graph, every other vertex has an edge from v or to v. These vertices are be split up into two sets, From and To, where From contains all the vertices with an edge from v and To contains all the vertices with an edge to v. By the inductive hypothesis, we know that both From and To are smaller versions of the larger tournament so there is a Hamiltonian path in both From and To. These two Hamiltonian paths can be join by the edge To v and the edge From v to form a Hamiltonian path throughout the entire graph. Thus there is a Hamiltonian path in the tournament graph n + 1 so, by strong induction, there is a Hamiltonian path in every tournament graph.