In the mathematical area of graph theory, a clique (/ˈkliːk/ or /ˈklɪk/) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph is an induced subgraph of that is complete. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in computer science: the task of finding whether there is a clique of a given size in a graph (the clique problem) is NP-complete, but despite this hardness result, many algorithms for finding cliques have been studied.
A graph with
23 × 1-vertex cliques (the vertices),
42 × 2-vertex cliques (the edges),
19 × 3-vertex cliques (light and dark blue triangles), and
2 × 4-vertex cliques (dark blue areas).
The 11 light blue triangles form maximal cliques. The two dark blue 4-cliques are both maximum and maximal, and the clique number of the graph is 4.
A clique, C, in an undirected graphG = (V, E) is a subset of the vertices, C ⊆ V, such that every two distinct vertices are adjacent. This is equivalent to the condition that the induced subgraph of G induced by C is a complete graph. In some cases, the term clique may also refer to the subgraph directly.
A maximal clique is a clique that cannot be extended by including one more adjacent vertex, that is, a clique which does not exist exclusively within the vertex set of a larger clique. Some authors define cliques in a way that requires them to be maximal, and use other terminology for complete subgraphs that are not maximal.
A maximum clique of a graph, G, is a clique, such that there is no clique with more vertices. Moreover, the clique numberω(G) of a graph G is the number of vertices in a maximum clique in G.
The intersection number of G is the smallest number of cliques that together cover all edges of G.
The clique cover number of a graph G is the smallest number of cliques of G whose union covers the set of vertices V of the graph.
A maximum clique transversal of a graph is a subset of vertices with the property that each maximum clique of the graph contains at least one vertex in the subset.
The opposite of a clique is an independent set, in the sense that every clique corresponds to an independent set in the complement graph. The clique cover problem concerns finding as few cliques as possible that include every vertex in the graph.
Mathematical results concerning cliques include the following.
Turán's theorem gives a lower bound on the size of a clique in dense graphs. If a graph has sufficiently many edges, it must contain a large clique. For instance, every graph with vertices and more than edges must contain a three-vertex clique.
According to a result of Moon & Moser (1965), a graph with 3n vertices can have at most 3n maximal cliques. The graphs meeting this bound are the Moon–Moser graphs K3,3,..., a special case of the Turán graphs arising as the extremal cases in Turán's theorem.
A simplex graph is an undirected graph κ(G) with a vertex for every clique in a graph G and an edge connecting two cliques that differ by a single vertex. It is an example of median graph, and is associated with a median algebra on the cliques of a graph: the median m(A,B,C) of three cliques A, B, and C is the clique whose vertices belong to at least two of the cliques A, B, and C.
The clique-sum is a method for combining two graphs by merging them along a shared clique.
Clique-width is a notion of the complexity of a graph in terms of the minimum number of distinct vertex labels needed to build up the graph from disjoint unions, relabeling operations, and operations that connect all pairs of vertices with given labels. The graphs with clique-width one are exactly the disjoint unions of cliques.
The intersection number of a graph is the minimum number of cliques needed to cover all the graph's edges.
Alba, Richard D. (1973), "A graph-theoretic definition of a sociometric clique" (PDF), Journal of Mathematical Sociology, 3 (1): 113–126, doi:10.1080/0022250X.1973.9989826.
Barthélemy, J.-P.; Leclerc, B.; Monjardet, B. (1986), "On the use of ordered sets in problems of comparison and consensus of classifications", Journal of Classification, 3 (2): 187–224, doi:10.1007/BF01894188, S2CID 6092438.
Chang, Maw-Shang; Kloks, Ton; Lee, Chuan-Min (2001), "Maximum clique transversals", Graph-theoretic concepts in computer science (Boltenhagen, 2001), Lecture Notes in Comput. Sci., vol. 2204, Springer, Berlin, pp. 32–43, doi:10.1007/3-540-45477-2_5, ISBN 978-3-540-42707-0, MR 1905299.
Cong, J.; Smith, M. (1993), "A parallel bottom-up clustering algorithm with applications to circuit partitioning in VLSI design", Proc. 30th International Design Automation Conference, pp. 755–760, CiteSeerX10.1.1.32.735, doi:10.1145/157485.165119, ISBN 978-0897915779, S2CID 525253.
Day, William H. E.; Sankoff, David (1986), "Computational complexity of inferring phylogenies by compatibility", Systematic Zoology, 35 (2): 224–229, doi:10.2307/2413432, JSTOR 2413432.
Doreian, Patrick; Woodard, Katherine L. (1994), "Defining and locating cores and boundaries of social networks", Social Networks, 16 (4): 267–293, doi:10.1016/0378-8733(94)90013-2.
Hamzaoglu, I.; Patel, J. H. (1998), "Test set compaction algorithms for combinational circuits", Proc. 1998 IEEE/ACM International Conference on Computer-Aided Design, pp. 283–289, doi:10.1145/288548.288615, ISBN 978-1581130089, S2CID 12258606.
Karp, Richard M. (1972), "Reducibility among combinatorial problems", in Miller, R. E.; Thatcher, J. W. (eds.), Complexity of Computer Computations(PDF), New York: Plenum, pp. 85–103, archived from the original (PDF) on 2011-06-29, retrieved 2009-12-13.
Kuhl, F. S.; Crippen, G. M.; Friesen, D. K. (1983), "A combinatorial algorithm for calculating ligand binding", Journal of Computational Chemistry, 5 (1): 24–34, doi:10.1002/jcc.540050105, S2CID 122923018.
Kuratowski, Kazimierz (1930), "Sur le problème des courbes gauches en Topologie" (PDF), Fundamenta Mathematicae (in French), 15: 271–283, doi:10.4064/fm-15-1-271-283.
Paull, M. C.; Unger, S. H. (1959), "Minimizing the number of states in incompletely specified sequential switching functions", IRE Transactions on Electronic Computers, EC-8 (3): 356–367, doi:10.1109/TEC.1959.5222697.
Peay, Edmund R. (1974), "Hierarchical clique structures", Sociometry, 37 (1): 54–65, doi:10.2307/2786466, JSTOR 2786466.
Prihar, Z. (1956), "Topological properties of telecommunications networks", Proceedings of the IRE, 44 (7): 927–933, doi:10.1109/JRPROC.1956.275149, S2CID 51654879.
Rhodes, Nicholas; Willett, Peter; Calvet, Alain; Dunbar, James B.; Humblet, Christine (2003), "CLIP: similarity searching of 3D databases using clique detection", Journal of Chemical Information and Computer Sciences, 43 (2): 443–448, doi:10.1021/ci025605o, PMID12653507.
Samudrala, Ram; Moult, John (1998), "A graph-theoretic algorithm for comparative modeling of protein structure", Journal of Molecular Biology, 279 (1): 287–302, CiteSeerX10.1.1.64.8918, doi:10.1006/jmbi.1998.1689, PMID9636717.