K₅, 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. In Mathematics and Computer science, graph theory is the study of graphs: mathematical structures used to model pairwise relations between objects In Mathematics and Computer science, a graph is the basic object of study in Graph theory. For other uses see Vertex. In Graph theory, a vertex (plural vertices) or node is the fundamental unit out In Mathematics and Computer science, a graph is the basic object of study in Graph theory. Alternatively, a clique is a graph in which every vertex is connected to every other vertex in the graph. This is equivalent to saying that the subgraph induced by V is a complete graph. In the mathematical field of Graph theory, a complete graph is a Simple graph in which every pair of distinct vertices is connected by an The size of a clique is the number of vertices it contains.

Finding whether there is a clique of a given size in a graph (the clique problem) is NP-complete. In Mathematics and Computer science, a graph is the basic object of study in Graph theory. In Computational complexity theory, the clique problem is a graph-theoretic NP-complete problem In Computational complexity theory, the Complexity class NP-complete (abbreviated NP-C or NPC) is a class of problems having two properties

The opposite of a clique is an independent set, in the sense that every clique corresponds to an independent set in the complement graph. In Graph theory, an independent set or stable set is a set of vertices in a graph no two of which are adjacent In Graph theory the complement or inverse of a graph G is a graph H on the same vertices

The term presumably comes from the idea that if the vertices represent people and the edges represent the relation 'knows', then everyone knows everyone else, thus forming a clique. A clique ( IPA:/'klɪk/ in America /'kliːk/ elsewhere is an exclusive group of people who share interests views purposes patterns of behavior or ethnicity

Subgraphs of a graph which are cliques may be referred to as cliques in the graph. The largest clique in a graph G is of theoretical importance and denoted ω(G). ^[1]

Notes

See also

• Solving the Maximum common subgraph isomorphism problem
• Maximal clique

References

• Godsil, Chris; Gordon Royle [1949] (2004). In complexity theory, maximum common subgraph-isomorphism (MCS is an Optimization problem that is known to be NP-hard. In Graph theory, a maximal independent set or maximal stable set is an Independent set that is not a subset of any other independent set Algebraic Graph Theory. New York: Springer. ISBN 0-387-95220-9.