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).