Question 5: Tyler is not only your friendly TA, he is also the inventor of Tyler paths and Tyler cycles in graphs: A Tyler path in an undirected graph is a path that contains every vertex exactly once. In the figure below, you see a Tyler path in red. A Tyler cycle is a cycle that contains every vertex exactly once. In the figure below, if you add the black edge {s,t} to the red Tyler path, then you obtain a Tyler cycle. If G=(V,E) is an undirected graph, then the graph G3 is defined as follows: 1. The vertex set of G3 is equal to V. 2. For any two distinct vertices u and v in V,{u,v} is an edge in G3 if and only if there is a path in G between u and v consisting of at most three edges. Question 5.1: Describe a recursive algorithm TYLERPATH that has the following specification: \begin{tabular}{l} Algorithm TYLerPath (T,u,v): \\ Input: A tree T with at least two vertices; two distinct vertices u and v in T such \\ that {u,v} is an edge in T. \\ Output: A Tyler path in T3 that starts at vertex u and ends at vertex v. \\ \hline \end{tabular} Hint: You do not have to analyze the running time. The base case is easy. Now assume that T has at least three vertices. If you remove the edge {u,v} from T, then you obtain two trees Tu (containing u ) and Tv (containing v ). 1. One of these two trees, say, Tu, may consist of the single vertex u. How does your recursive algorithm proceed? 2. If each of Tu and Tv has at least two vertices, how does your recursive algorithm proceed? Question 5.2: Prove the following lemma: Tuttle's Lemma: For every tree T that has at least three vertices, the graph T3 contains a Tyler cycle. Question 5.3: Prove the following theorem: Tuttle's Theorem: For every connected undirected graph G that has at least three vertices, the graph G3 contains a Tyler cycle. Algorithm DFS (G) : for each vertex u do visited (u)= false endfor; cc=0; for each vertex v do if visited (v)= false then cc=cc+1 ExploRe(v) endif endfor Algorithm Explore (v) : visited (v)= true ccnumber (v)=cc; for each edge {v,u} do if visited (u)= false then ExPLORE(u) endif endfor