Problem 6 [20 pts]: High School Cliques and Completeness Let G = (V, E) be a graph with |V | = n vertices. G is a complete graph of n vertices, if for every pair of vertices u, v V , u 6= v, (u, v) E. We call a complete graph of n vertices, Kn. We may also consider a complete subgraph of G, called a clique. A k-clique is a clique of k verticies

fo kti Figure 3: A visual representation of the hint. We have the k + 1th vertex. The cloud to the left represents the subgraph with vertices that point to the k + 1th vertex. The cloud to the right represents the subgraph with vertices that the k +1th vertex points to. iii. * Let H be an undirected complete graph of n vertices. Suppose H' is a directed graph that has been created by taking H and imposing an arbitrary direction on cach edge; thus if {a,b} is an edge in H, (a,b) or (b, a) is an edge in H' (but not both). Prove by strong induction on the size of the nunmber of vertices n that there is always a path that hits all vertices in the complete graph, even in the directed version of the graph, for n > 1. Hint: consider what happens when you add a new vertex to the complete graph. You will end up with a situation like Figure 3. Apply the inductive hypothesis to the set of vertices that have incoming edges to that vertex as well as the set of vertices that the new vertex can reach in one step. Can you argue there must still be a path? fo kti Figure 3: A visual representation of the hint. We have the k + 1th vertex. The cloud to the left represents the subgraph with vertices that point to the k + 1th vertex. The cloud to the right represents the subgraph with vertices that the k +1th vertex points to. iii. * Let H be an undirected complete graph of n vertices. Suppose H' is a directed graph that has been created by taking H and imposing an arbitrary direction on cach edge; thus if {a,b} is an edge in H, (a,b) or (b, a) is an edge in H' (but not both). Prove by strong induction on the size of the nunmber of vertices n that there is always a path that hits all vertices in the complete graph, even in the directed version of the graph, for n > 1. Hint: consider what happens when you add a new vertex to the complete graph. You will end up with a situation like Figure 3. Apply the inductive hypothesis to the set of vertices that have incoming edges to that vertex as well as the set of vertices that the new vertex can reach in one step. Can you argue there must still be a path