Complete graph

The complete graph $K_r$ has $r$ vertices and every possible edge between distinct vertices.

A clique in a graph is a vertex set whose induced subgraph is complete. A copy of $K_r$ is therefore an $r$-vertex clique.

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.

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 maximum number of vertices in a clique of a graph. If the graph contains $K_k$ and no $K_{k+1}$, its clique number is exactly $k$, since every larger clique contains a $(k+1)$-clique.

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