(a) Use induction to prove the following statement:
T$_n$ has a directed hamiltonian path (a directed path that visits all vertices).
let starts with 2 vertices, so there is only one edge is present, so there should be Hamilton-path exist !
now add one more vertex to the group. let called it as V$_3$.
Now we have an edge between V$_1$ and V$_3$. one more edge between V$_2$ and V$_3$.
But we don't the directions, So there are 2 edges, each edge may up or down (i.e,. 2 possibilities) ==> 2$^2$ = 4 possibilities of graphs.
So, from above picture, you can understood that, every possibility have atleast one Hamilton path ( But not Hamilton Cycle.)
But how can we say in general ?
already existing Hamilton path is 1 --> 2, New vertex is 3
There should be an edge between 3 and 1,
$\color{green}{\text{suppose it is 3 --> 1, then already we have 1 --> 2, So Hamilton Path is 3 --> 1 --> 2 exist !} }$
$\color{green}{\text{( no need to worry about the edge between 2 and 3 )}}$
$\color{red}{\text{ suppose it is 1 --> 3, ( just wait )}}$
There should be an edge between 3 and 2,
suppose if it is 2 --> 3, then already we have 1 --> 2, So Hamilton Path is 1 --> 2 --> 3 exist !
( no need to worry about the edge between 1 and 3 )
suppose if it is 3 --> 2, ( considering the red case only due to ), you have 1 --> 3 ---> 2 as Hamilton Path.
Assume :-
given statement is true for n vertices, we have to show it is true for n+1 vertices.
for simplicity assume the Hamilton Path of n vertices is like V$_1$ --> V$_2$ --> V$_3$ --> V$_4$ --> .......--> V$_{n-1}$ --> V$_n$ .
let the new vertex V$_{n+1}$,
if the edge between V$_{n+1}$ and V$_{1}$ is like V$_{n+1}$ to V$_{1}$ then
V$_{n+1}$ --> V$_1$ --> V$_2$ --> V$_3$ --> V$_4$ --> .......--> V$_{n-1}$ --> V$_n$ is Hamilton Path.
else if the edge between V$_{n+1}$ and V$_{2}$ is like V$_{n+1}$ to V$_{2}$ then
V$_1$ --> V$_{n+1}$ --> V$_2$ --> V$_3$ --> V$_4$ --> .......--> V$_{n-1}$ --> V$_n$ is Hamilton Path.
else if the edge between V$_{n+1}$ and V$_{3}$ is like V$_{n+1}$ to V$_{3}$ then
V$_1$ --> V$_2$ --> V$_{n+1}$ --> V$_3$ --> V$_4$ --> .......--> V$_{n-1}$ --> V$_n$ is Hamilton Path.
..............
else if the edge between V$_{n+1}$ and V$_{n}$ is like V$_{n+1}$ to V$_{n}$ then
V$_1$ --> V$_2$ --> V$_3$ --> V$_4$ --> .......--> V$_{n-1}$ --> V$_{n+1}$ --> V$_n$ is Hamilton Path.
else the edge between V$_{n}$ and V$_{n+1}$ is like V$_{n}$ to V$_{n+1}$ then
V$_1$ --> V$_2$ --> V$_3$ --> V$_4$ --> .......--> V$_{n-1}$ --> V$_{n}$ --> V$_{n+1}$ is Hamilton Path.
(b) Describe an algorithm that finds a directed hamiltonian path in a given tournament. Do not write whole programs; pseudocode, or a simple description of the steps in the algorithm, will suffice. What is the worst case time complexity of
your algorithm?
It is nothing but Topological sorting. TC = O(V+E).
https://www.geeksforgeeks.org/topological-sorting/
