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≠v, (u, v) ∈ E. We call a complete graph of n vertices, Kₙ. We may also consider a complete subgraph of G, called a clique. A k-clique is a clique of k vertices.
i. Given a value n, how many edges are in Kₙ? =
ii. Given a value k = |V|, how many possible k-cliques are there in an undirected graph G = (V, E)?
iii. Given a graph G and k where 1 ≤ k ≤ |V|, we can check to see if it has a clique by checking every possible combination of k vertices, and check if there exists an edge between all pairs. At worst, how many edges do you have to check exist or not?
iv. Suppose we wish to assign colors to each vertex in a graph G such that no two vertices that are connected by an edge share a color. If a graph has a k-clique, at least how many colors do you need to color that graph under our rules? Why?
v. Suppose G' is a directed graph that has been created by taking undirected graph G and imposing an arbitrary direction on each edge; thus if {a,b} is an edge in G, (a,b) or (b, a) is an edge in G' (but not both). Prove by strong induction on the size of the clique k that there is always a path that hits all vertices in the clique, even in the directed version of the clique, for k ≥ 1. Hint: consider what happens when you add a new vertex to the clique, and 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?