## hasClique

Language/Type: C++ Graph collections
Author: Marty Stepp (on 2016/06/16)

Write a function named `hasClique` that accepts two parameters: a reference to a BasicGraph, and an integer K. The goal of your function is to see whether it is possible to form a "clique" of K vertexes in the given graph. In graph theory, a clique is a strongly connected subset of vertexes such that every pair of vertexes in the clique is connected by an edge. Trivially, every vertex itself is a 1-clique, and every pair of vertexes directly connected by an edge is a 2-clique. A 3-clique would be a triangle with each vertex connected to every other; a 4-clique would be 4 vertexes with edges between every pair of them; and so on. The diagram below shows examples of various cliques.

Graph 1 with a 3-clique: {1, 2, 5}
Graph 2 with a 4-clique: {d, g, n, r}

If your function were passed the above Graph 1 and the K value of 3 or less, should return the boolean result of `true` to indicate that a suitable clique does exist. If passed a larger value, your function should return `false`. (The graph might have just one clique of the given size, or many, or none at all.) If your function were passed the graph above at right and a K value of 4 or less, it would similarly return `true`, but would return `false` for K values of 5 or above because no such clique exists in that graph.

You may assume that the graph's state is valid, and that it is undirected and unweighted, and that it contains no self-edges (e.g. from V1 to V1). You may define private helper functions if so desired, and you may construct auxiliary collections as needed to solve this problem. You should not modify the contents of the graph such as by adding or removing vertexes or edges from the graph, though you may modify the state variables inside individual vertexes/edges such as visited, cost, and color.

You may assume that the K value passed is 1 or greater.

Hint: Your algorithm for solving this problem does not need to try to be optimal or clever. Consider exhaustively trying possible arrangements of vertexes to see whether a clique of the given size can be found.

Type your C++ solution code here:

This is a function problem. Write a C++ function as described. Do not write a complete program; just the function(s) above.