Editing Tournament (graph theory) (section)

== Paths and cycles ==
[[Image:Tournament Hamiltonian path.svg|thumb|{{mvar|a}} is inserted between {{math|''v''{{sub|2}}}} and {{math|''v''{{sub|3}}}}.]]
Any tournament on a [[finite set|finite]] number <math>n</math> of vertices contains a [[Hamiltonian path]], i.e., directed path on all <math>n</math> vertices ([[László Rédei|Rédei]] 1934).

This is easily shown by [[Mathematical induction|induction]] on <math>n</math>: suppose that the statement holds for <math>n</math>, and consider any tournament <math>T</math> on <math>n+1</math> vertices. Choose a vertex <math>v_0</math> of <math>T</math> and consider a directed path <math>v_1,v_2,\ldots,v_n</math> in <math>T\smallsetminus \{v_0\}</math>. There is some <math>i \in \{0,\ldots,n\}</math> such that <math>(i=0 \vee v_i \rightarrow v_0) \wedge (v_0 \rightarrow v_{i+1} \vee i=n)</math>. (One possibility is to let <math>i \in \{0,\ldots,n\}</math> be maximal such that for every <math>j \leq i, v_j \rightarrow v_0</math>. Alternatively, let <math>i</math> be minimal such that <math>\forall j > i, v_0 \rightarrow v_j</math>.)
<math display="block">v_1,\ldots,v_i,v_0,v_{i+1},\ldots,v_n</math>
is a directed path as desired. This argument also gives an algorithm for finding the Hamiltonian path. More efficient algorithms,  that require examining only <math>O(n \log n)</math> of the edges, are known. The Hamiltonian paths are in one-to-one correspondence with the minimal [[feedback arc set]]s of the tournament.{{sfnp|Bar-Noy|Naor|1990}} Rédei's theorem is the special case for complete graphs of the [[Gallai–Hasse–Roy–Vitaver theorem]], relating the lengths of paths in orientations of graphs to the [[chromatic number]] of these graphs.{{sfnp|Havet|2013}}

Another basic result on tournaments is that every [[strongly connected component|strongly connected]] tournament has a [[Hamiltonian cycle]].{{sfnp|Camion|1959}} More strongly, every strongly connected tournament is [[pancyclic graph|vertex pancyclic]]: for each vertex <math>v</math>, and each <math>k</math> in the range from three to the number of vertices in the tournament, there is a cycle of length <math>k</math> containing <math>v</math>.{{sfnp|Moon|1966|loc=Theorem 1}} A tournament <math>T</math> is <math>k</math>-strongly connected if for every set <math>U</math> of <math>k-1</math> vertices of <math>T</math>, <math>T-U</math> is strongly connected. 
If the tournament is 4‑strongly connected, then each pair of vertices can be connected with a Hamiltonian path.{{sfnp|Thomassen|1980}} For every set <math>B</math> of at most <math>k-1</math> arcs of a <math>k</math>-strongly connected tournament <math>T</math>, we have that <math>T-B</math> has a Hamiltonian cycle.{{sfnp|Fraisse|Thomassen|1987}} This result was extended by {{harvtxt|Bang-Jensen|Gutin|Yeo|1997}}.{{sfnp|Bang-Jensen|Gutin|Yeo|1997}}