# Clique (graph theory)

Missing image
Complete_graph_K5.png
K5, a complete graph. If a subgraph looks like this, the vertices in that subgraph form a clique of size 5.

In graph theory, a clique in an undirected graph G, is a set of vertices V such that for every two vertices in V, there exists an edge connecting the two. This is equivalent to saying that the subgraph induced by V is a complete graph. 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 |V′|=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 complement graph.de:Vollständiger Graph pl:Klika (teoria grafów)

• Art and Cultures
• Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
• Space and Astronomy