4clique

In graph theory, a 4-clique, also called a K4, is a complete subgraph on four vertices. This means the four vertices are pairwise adjacent, forming a subgraph with exactly six edges. A 4-clique is a specific instance of a clique; it denotes a four-vertex clique, though it may be contained within a larger clique such as a K5.

In a larger graph, a 4-clique consists of four vertices where every pair among them is connected by an edge. A 4-clique can appear as a subgraph of larger structures; for example, a K5 contains many 4-cliques as subgraphs. Key properties include that each vertex of a 4-clique has degree 3 within the subgraph, the edge count is 6, and the chromatic number of K4 is 4. The existence of a 4-clique implies a clique number of at least 4 for the graph.

Detection and counting: A common approach to testing for a 4-clique is to examine each vertex v, consider its neighborhood N(v), and check whether N(v) contains a triangle. If N(v) contains a triangle among vertices a, b, and c, then {v, a, b, c} forms a 4-clique. Counting all 4-cliques can be done by aggregating the number of triangles found within neighborhood subgraphs across all vertices.

Complexity: For fixed k, the k-clique problem is solvable in polynomial time; naive enumeration for k = 4 runs in O(n^4) time, with practical improvements by leveraging neighborhood structures to achieve O(n^3) in many implementations. Theoretical algorithms using fast matrix multiplication can achieve subcubic time in certain models.

See also: clique, k-clique, K4, clique problem.