# All Science Fair Projects

## Science Fair Project Encyclopedia for Schools!

 Search    Browse    Forum  Coach    Links    Editor    Help    Tell-a-Friend    Encyclopedia    Dictionary

# Science Fair Project Encyclopedia

For information on any area of science that interests you,
enter a keyword (eg. scientific method, molecule, cloud, carbohydrate etc.).
Or else, you can start by choosing any of the categories below.

# Clique (graph theory)

In graph theory, a clique in a undirected graph G, is a set of vertices V such that for every two vertices in V, there exists an edge connecting the two. Additionally, this means that a clique is simply a complete subgraph of G. The size of a clique is the number of vertices it contains.

The clique problem refers to the problem of finding the largest clique in any graph G. This problem is NP-complete, and as such, many consider that it is unlikely that an efficient algorithm for finding the largest clique of a graph exists.

A k-clique is a clique of size k. Therefore, the k-clique problem refers to the problem of finding a clique of size k, i.e. a complete subgraph G′(V′,E′) of G with |E′|=k. A k-clique can be found using a brute-force algorithm in O(nk) time.

The opposite of a clique is an independent set. If we already know that the independent set problem is NP-complete, then it is easy to prove, as the size of the largest clique is the same as the size of the largest independent set in the inverse graph.

03-10-2013 05:06:04