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 each 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? 1.1.11. Determine the maximum size of a clique and the maximum size of an indepen- dent set in the graph below. 1.1.12. Determine whether the Petersen graph is bipartite, and find the size of its largest independent set. 1.1.13. Let G be the graph whose vertex set is the set of k-tuples with coordinates in {0, 1}, with x adjacent to y when x and y differ in exactly one position. Determine whether G is bipartite.