Complete Graphs
A complete graph is the most connected simple graph possible on a fixed vertex set: every pair of distinct vertices is joined by an edge. It is a useful reference when describing how many edges a graph could have and when looking for tightly connected groups within a larger graph. In this tutorial, all graphs are finite and simple, so they have no loops or multiple edges.
For example, \(K_4\) has vertex set \(V=\{1,2,3,4\}\) and edge set \(E=\{12,13,14,23,24,34\}\). Each vertex is adjacent to the other three. By contrast, a graph on four vertices with only five edges is not complete, because at least one pair of vertices is not adjacent.
A complete graph is a graph in its own right. A complete subgraph is a subgraph of a possibly larger graph that is complete. More precisely, a graph \(H\) is a subgraph of \(G\) if \(V(H)\subseteq V(G)\) and \(E(H)\subseteq E(G)\), with every edge of \(H\) having both endpoints in \(V(H)\). A set \(S\) of vertices is a clique if every two distinct vertices in \(S\) are adjacent in \(G\). For a nonempty \(S\), this is equivalent to saying that the induced subgraph \(G[S]\) is complete. A clique with \(r\) vertices gives a complete subgraph isomorphic to \(K_r\).
The phrase “complete subgraph” does not mean that the whole graph is complete. For instance, a graph may contain three mutually adjacent vertices, and therefore a copy of \(K_3\), while other vertices in the graph have missing edges. This is why identifying cliques requires checking the edges among a chosen set, not just counting edges in the entire graph.
Counting the Edges of \(K_n\)
Proof. An edge in a simple graph joins two distinct vertices, and its endpoints form an unordered pair. In \(K_n\), every unordered pair of distinct vertices is an edge, and each such pair gives exactly one edge. Therefore the number of edges is the number of ways to choose two vertices from \(n\), which is \(\binom{n}{2}=n(n-1)/2\). This also covers \(n=0\) and \(n=1\): there are no pairs of distinct vertices, and the formula gives \(0\) in both cases. \(\square\)
There is a related degree check. Each vertex of \(K_n\) has degree \(n-1\), because it is adjacent to all the other vertices. For \(n\ge 1\), the sum of the degrees is \(n(n-1)\); the handshake lemma counts each edge twice in that sum, giving \(2|E(K_n)|=n(n-1)\) and the same formula. For \(K_0\), there are no vertices or edges, so the formula still holds directly.
Worked Example: Counting the Edges of \(K_5\)
Let \(K_5\) have vertex set \(V=\{1,2,3,4,5\}\) and edge set \(E=\{12,13,14,15,23,24,25,34,35,45\}\). The formula gives \(\binom{5}{2}=5\cdot4/2=20/2=10\) edges.
To check directly, list the edges by their smaller endpoint: vertex \(1\) gives \(12,13,14,15\); vertex \(2\) gives \(23,24,25\); vertex \(3\) gives \(34,35\); and vertex \(4\) gives \(45\). The total is \(4+3+2+1=10\). Each vertex has degree \(4\), so the degree sum is \(5\cdot4=20\), and dividing by \(2\) gives \(20/2=10\) edges, as required.
Check: the displayed edge set contains \(4+3+2+1=10\) distinct pairs, and the formula independently gives \(5(5-1)/2=20/2=10\).
Finding Complete Subgraphs
To test whether a set \(S\) is a clique, check every pair of distinct vertices in \(S\). If \(|S|=r\), the set must contain all \(\binom{r}{2}=r(r-1)/2\) possible edges among those vertices. Having that many edges somewhere in the graph is not sufficient: the required edges must join pairs from \(S\). Conversely, once every pair in \(S\) is an edge, \(S\) is a clique, regardless of which edges join its vertices to vertices outside \(S\).
Proof. Suppose \(S\) is a clique. By definition, every pair of distinct vertices in \(S\) is adjacent, so all \(\binom{r}{2}\) possible edges within \(S\) are present. Conversely, suppose all those possible edges are present. Then each pair of distinct vertices in \(S\) is adjacent, which is exactly the definition of a clique. When \(r=1\), there are no pairs to check, and the single vertex is a clique under this definition. \(\square\)
In a complete graph \(K_n\), every subset of \(r\) vertices is a clique, provided \(1\le r\le n\). Thus \(K_n\) contains \(\binom{n}{r}\) different vertex sets of size \(r\), each inducing a complete subgraph. Indeed, selecting an \(r\)-vertex subset gives a clique, and every \(r\)-vertex clique in \(K_n\) is such a subset. This counts vertex sets, not different ways of drawing or naming the same subgraph.
Worked Example: Triangles in a Graph with a \(K_4\)
Let \(G\) have vertex set \(V=\{1,2,3,4,5\}\) and edge set \(E=\{12,13,14,23,24,34,35,45\}\). The vertices \(\{1,2,3,4\}\) have all six possible internal edges \(12,13,14,23,24,34\), so they form a \(K_4\).
Find all triangles by testing the \(\binom{5}{3}=5!/(3!2!)=10\) three-vertex subsets. The four subsets contained in \(\{1,2,3,4\}\), namely \(\{1,2,3\}\), \(\{1,2,4\}\), \(\{1,3,4\}\), and \(\{2,3,4\}\), are triangles because all three edges for each subset are present.
The other six subsets each include vertex \(5\). For \(\{1,2,5\}\), edges \(15\) and \(25\) are absent. For \(\{1,3,5\}\), edge \(15\) is absent. For \(\{1,4,5\}\), edge \(15\) is absent. For \(\{2,3,5\}\), edge \(25\) is absent, although \(23\) is present. For \(\{2,4,5\}\), edge \(25\) is absent. For \(\{3,4,5\}\), all three edges \(34,35,45\) are present, so this is one more triangle. The complete list is therefore \(\{1,2,3\}\), \(\{1,2,4\}\), \(\{1,3,4\}\), \(\{2,3,4\}\), and \(\{3,4,5\}\): five triangles.
Check: the degrees are \(3,3,4,4,2\), respectively, so their sum is \(3+3+4+4+2=16\). The edge set has \(8\) edges, and \(2|E|=2\cdot8=16\), agreeing with the handshake lemma. For an independent triangle count, each triangle contributes once to the common-neighbor count at each of its three edges. The six edges of the \(K_4\) have common-neighbor counts \(2,2,2,2,2,3\), which sum to \(13\); edges \(35\) and \(45\) each have common-neighbor count \(1\), bringing the total to \(15\). Thus the number of triangles is \(15/3=5\), matching the list.
Worked Example: A Largest Clique of Size Three
Let \(G\) have vertex set \(V=\{1,2,3,4,5,6\}\) and edge set \(E=\{12,13,23,34,45,56\}\). The set \(\{1,2,3\}\) is a clique: its three possible edges \(12,13,23\) are all present. Hence \(G\) contains a \(K_3\).
There is no clique with four or more vertices. To check this, note that vertices \(1\) and \(2\) are adjacent only to each other and to \(3\). Any clique containing \(1\) or \(2\) can therefore include only vertices among \(\{1,2,3\}\). Among the remaining vertices \(\{3,4,5,6\}\), the edges are \(34,45,56\), which form a path and contain no triangle: there is no edge \(35\), \(36\), or \(46\) to complete a three-vertex clique. Thus no four-vertex clique exists, and the largest clique has size three.
Check: the edge list contains \(6\) edges. The degrees are \(2,2,3,2,2,1\), whose sum is \(2+2+3+2+2+1=12=2\cdot6\). The triangle \(\{1,2,3\}\) is verified by its three listed edges; the absence of any other triangle follows from the edge checks above.
Common Pitfalls and Uses
Do not count ordered pairs as edges. A common wrong calculation for \(K_4\) is \(4(4-1)=12\) edges, obtained by counting each vertex's three neighbors and adding the degrees. But each edge is counted from both endpoints. The correction is \(12/2=6\), which agrees with \(\binom{4}{2}=4\cdot3/2=6\). The degree sum is useful as a check, but it is twice the edge count.
Do not infer a clique from the total number of edges. A graph might have many edges but still omit an edge among a particular proposed set of vertices. For example, in the graph in the triangle example, the set \(\{1,2,5\}\) is not a triangle: even though the graph has eight edges overall, the required edges \(15\) and \(25\) are absent. Check the pairs within the candidate set one by one.
Complete graphs and their subgraphs give two useful kinds of information. The formula for \(K_n\) supplies the maximum possible number of edges on \(n\) vertices. Searching for cliques, in contrast, locates subsets that are completely connected even when the whole graph is not. In an explicit graph, a reliable method is to list candidate vertex subsets, check every internal pair, and record a subset only when none of its required edges is missing.
Check Your Understanding
For each question, specify the relevant vertex set or edge set and show the pair checks or arithmetic used.
- How many edges does \(K_6\) have? Verify the answer by summing its vertex degrees and dividing by \(2\).
- In the graph with \(V=\{a,b,c,d\}\) and \(E=\{ab,ac,bc,cd\}\), which vertex sets of size three are cliques?
- Give the edge set of a complete graph on four vertices, and explain why it has exactly six edges.
- Can a graph contain a \(K_4\) and also have vertices outside that \(K_4\)? Explain what must be present among the four clique vertices and what need not be present elsewhere.
- For a graph on five vertices, how many three-vertex subsets must be tested to find all triangles? Show the binomial-coefficient calculation.