Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
Definition 1 looks weird, what is $e$? –  fgp Mar 20 at 20:29
    
I'm guessing that was edges but I am not sure myself. –  DrJonesYu Mar 20 at 20:31
1  
According to en.wikipedia.org/wiki/Tournament_%28graph_theory%29, it should read "...exactly one of $(u,v)$ or $(v,u)$ are in E.", not "... or $(v,e)$". Thus, a turnament graph is a directed graph that becomes the complete graph if you ignore the directions... –  fgp Mar 20 at 20:33
    
Thanks for the catch. –  DrJonesYu Mar 20 at 20:35
1  
And you state the induction hypothesis incorrectly. It's true that vertices $1,\ldots,n$ contain a hamiltonian path, but that not sufficient for the rest of your proof - you need that all subgraphs contain one. You actually do state that later, so just drop the confusing statement about the first $n$ vertices. Just say "Pick a vertex, partition the graph into sets TO and FROM (disjoint!), both contain a hamiltonian path per the induction hypothesis, and thus $P_{FROM} \to v \to P_{TO}$ is a hamiltonian path." –  fgp Mar 20 at 20:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.