Complete graph ($K_n$)

A complete graph is a simple graph in which every two distinct vertices are joined by an edge. The finite complete graph on $n$ vertices is denoted $K_n$. Here the edges are undirected, and self-loops are excluded. The usual pictures below use $n\ge 1$: $K_1$ is a single vertex, $K_2$ a single edge, and $K_3$ a triangle in a graph.^[ref]

Completeness describes all the possible pairs, rather than a drawing style. Different layouts can represent the same graph through a graph isomorphism. Crossing lines away from the drawn vertices do not add new vertices or edges.

There are $\left(\genfrac{}{}{0ex}{}{n}{2}\right)=n(n-1)/2$ unordered pairs of distinct vertices, so this is the edge count of a complete graph. Each vertex has vertex degree $n-1$. The degree-sum formula gives the same count: $2|E|=n(n-1)$. These formulas make a complete graph the upper extreme for edge counts among simple graphs of a fixed size.

This is useful when modelling pairwise relationships. If every pair of objects needs its own direct connection, ten vertices require $45$ edges, while twenty require $190$. Adding one more vertex to $K_n$ introduces $n$ further edges. This counts a specified direct-link model; it does not require every communication system to implement every relationship with a separate physical connection.

A proper vertex coloring of $K_n$ must give every vertex a different color, so its chromatic number is $n$. For $n\ge 1$, its independence number is $1$: two distinct vertices already have an edge between them. Thus complete graphs provide immediate test cases for graph coloring and independent sets.

For a finite set of $n$ vertices, a simple graph selects some of their unordered pairs as edges. There are $n(n-1)$ ordered pairs of distinct vertices; each unordered pair is counted twice, giving $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ possibilities. Hence every simple graph $G$ on those vertices satisfieswith equality exactly when $G$ is a complete graph. The binomial coefficient also shows why the count grows quadratically with the number of vertices.

A clique in a simple graph $G$ is a set $C$ of vertices such that every pair of distinct members is adjacent. Equivalently, its induced subgraph $G[C]$ is a complete graph. The surrounding graph need not itself be complete: a clique describes complete pairwise connectivity within a selected group.

Consider the original graph withThe set $\{a,b,c\}$ is a clique because all three pairs $ab,ac,bc$ are edges. The set $\{b,c,d\}$ is not a clique: the edge $bd$ is missing. A path in a graph connecting all selected vertices is therefore insufficient; every pair must have a direct edge.

Here the clique number is $3$. The maximum clique is $\{a,b,c\}$, but $\{c,d\}$ and $\{d,e\}$ are also maximal cliques. This distinction is useful when an algorithm stops as soon as its current clique cannot be enlarged: that stopping condition establishes maximality, while finding the largest possible clique is a separate requirement.

Given an explicitly represented finite simple graph $G$ and a nonnegative integer $k$, decide whether $G$ contains a clique of size $k$. The problem is NP-complete. A polynomial-time many-one reduction from SAT first obtains conjunctive normal form by a Tseitin transformation, makes one vertex per Boolean literal occurrence, and joins noncontradictory occurrences from different Boolean clauses. A clique as large as the Boolean clause count is equivalent to a satisfying assignment.

A maximum clique is a clique with the greatest possible number of vertices in the graph. Its size is the clique number. Every maximum clique is a maximal clique, since adding a vertex would produce a larger clique. A graph can have several maximum cliques; the word maximum specifies their common size, rather than uniqueness.

A maximal clique is a clique not strictly contained in another clique. This is distinct from a maximum clique, whose size equals the clique number. In a triangulated probabilistic graphical model, maximal cliques are the natural nodes of a junction tree.

Maximality is a condition on set inclusion: no outside vertex is adjacent to every member of the current clique. In the five-vertex example, $\{c,d\}$ is maximal because $a,b$ are not adjacent to $d$, while $e$ is not adjacent to $c$. Yet $\{a,b,c\}$ is larger. Checking every possible one-vertex extension is enough: if a larger containing clique existed, any one of its new vertices could already be added.^[ref]

An edge-disjoint clique packing is a collection of $r$-cliques no two of which share an edge; they may share vertices. Its maximum cardinality $Z_r(G)$ changes by at most one when a single edge is toggled. Removing that edge destroys at most one packed clique, which makes this variable suitable for an edge-exposure martingale.

Let $X$ count $k$-cliques in a binomial random graph on $m$ vertices and $Y$ count distinct ordered pairs sharing an edge. The clique conflict graph gives $Z_k\ge X^2/(X+Y)$: order its vertices randomly and keep each one preceding all its neighbours, then apply the Cauchy-Schwarz inequality. Another application gives $\mathbb{E}{Z}_k\ge (\mathbb{E}X{)}^2/(\mathbb{E}X+\mathbb{E}Y)$. If $\mathbb{E}Y/(\mathbb{E}X{)}^2=O(k^4/m^2)$ and $1/\mathbb{E}X$ is no larger, then $\mathbb{E}{Z}_k=\Omega (m^2/k^4)$. Changing one edge changes $Z_k$ by at most one, so the Azuma-Hoeffding inequality for an edge-exposure martingale yields the displayed exponential absence bound. This supports a union bound over exponentially many adaptive candidate subsets.

The clique conflict graph has one vertex for each $r$-clique of a fixed graph, and joins two when they share an edge. Its independent sets correspond exactly to edge-disjoint clique packings. The Caro-Wei bound converts clique-count and overlap estimates into a packing lower bound.

The clique number $\omega (G)$ is the maximum number of vertices in a clique of a finite graph:We use $\omega (G)=0$ for the graph with no vertices. For a nonempty complete graph, $\omega (K_n)=n$; for the five-vertex example, $\omega (G)=3$.

If the graph contains $K_k$ and no $K_{k+1}$ as subgraphs, its clique number is exactly $k$, because every larger clique contains a clique with $k+1$ vertices. Also $\chi (G)\ge \omega (G)$: a proper vertex coloring must assign different colors to all members of any clique. This lower bound need not be an equality; the cycle graph $C_5$ has clique number $2$ and chromatic number $3$.

A clique records pairwise relationships. If vertices represent sets and an edge means a nonempty intersection, a clique does not by itself guarantee an element common to every set. TakeThen $A\cap B=\{2\}$, $B\cap C=\{3\}$ and $C\cap A=\{1\}$, so their intersection graph is $K_3$. But $A\cap B\cap C=\varnothing$. The graph faithfully records all three pairwise intersections; the stronger claim of a single shared element requires additional hypotheses.

For the adjacency matrix $A$ of $K_n$,Hence $I,A,A^2$ are linearly dependent for every $n\ge 2$.