Parameters of a Complete Graph
Complete graphs are useful test cases because every pair of distinct vertices is adjacent. This makes their independent sets and cliques especially simple, while their matching and edge-cover numbers depend on how many vertices can be paired. The small cases matter: the empty graph has a vacuous edge cover, but the one-vertex graph does not.
All graphs in this tutorial are finite and simple. The complete graph \(K_n\) has \(n\) vertices and an edge between every pair of distinct vertices. We allow \(n=0\), so \(K_0\) has no vertices and no edges. A vertex cover is a set of vertices containing at least one endpoint of every edge; its minimum size is \(\tau(G)\). An independent set is a set of vertices with no edge between any two of them; its maximum size is \(\alpha(G)\). A clique is a set of pairwise adjacent vertices, and its maximum size is \(\omega(G)\). We count the empty set as both an independent set and a clique, so \(\alpha(K_0)=\omega(K_0)=0\).
A matching is a set of edges no two of which share an endpoint; the largest matching size is \(\nu(G)\). An edge cover is a set of edges such that every vertex is incident to at least one selected edge. When an edge cover exists, its minimum size is denoted by \(\rho(G)\). If no edge cover exists, \(\rho(G)\) is undefined.
Why the Formulas Hold
Proof. If \(n=0\), the only vertex subset is the empty set. It is both independent and a clique, so \(\alpha(K_0)=\omega(K_0)=0\). The empty set is also a vertex cover because there are no edges, giving \(\tau(K_0)=0\). If \(n\ge1\), any two distinct vertices of \(K_n\) are adjacent, so an independent set contains at most one vertex; a singleton is independent, hence \(\alpha(K_n)=1\). Every subset of \(V(K_n)\) is a clique, and the full vertex set is largest, so \(\omega(K_n)=n\).
For \(n\ge1\), a vertex cover must leave at most one vertex outside it: if it left two distinct vertices out, the edge between them would have neither endpoint in the cover. Thus every cover has size at least \(n-1\). Taking any \(n-1\) vertices gives a cover, because every edge has at least one endpoint among them. Therefore \(\tau(K_n)=n-1\). Together with the empty case, this proves the stated vertex-cover formula.
For a matching with \(r\) edges, its edges use \(2r\) distinct vertices, so \(2r\le n\) and \(r\le\lfloor n/2\rfloor\). To attain this bound, list the vertices as \(v_1,\ldots,v_n\) and select \(v_1v_2,v_3v_4,\ldots,v_{2r-1}v_{2r}\), where \(r=\lfloor n/2\rfloor\). Each listed pair is an edge because the graph is complete, and no two selected edges share a vertex. When \(n=0\) or \(n=1\), this construction selects no edges and the upper bound is zero. Hence \(\nu(K_n)=\lfloor n/2\rfloor\) for every \(n\ge0\).
For \(n=0\), the empty set of edges covers every vertex vacuously, so \(\rho(K_0)=0=\lceil0/2\rceil\). For \(n=1\), the sole vertex has no incident edge, so no edge set can cover it and \(\rho(K_1)\) is undefined. Now suppose \(n\ge2\). If an edge cover has \(q\) edges, those edges are incident to at most \(2q\) vertices, so \(2q\ge n\) and \(q\ge\lceil n/2\rceil\). For even \(n\), pair all vertices and select the \(n/2\) edges joining the pairs. This covers every vertex. For odd \(n\ge3\), pair \(n-1\) vertices and join the remaining vertex to one of the paired vertices. This uses \((n-1)/2+1=(n+1)/2=\lceil n/2\rceil\) edges and covers all vertices. The lower bound and constructions prove the edge-cover formula. \(\square\)
The vertex-cover argument also gives a direct connection with independent sets: a set \(S\) is a vertex cover exactly when its complement \(V\setminus S\) is independent. Indeed, an edge with both endpoints outside \(S\) is precisely an edge not covered by \(S\). In \(K_n\) with \(n\ge1\), the largest possible complement therefore has size one, yielding a minimum cover of size \(n-1\). For \(K_0\), both the cover and its complement are empty.
Worked Examples
Worked Example: The Empty Graph \(K_0\)
Let \(V(K_0)=\varnothing\) and \(E(K_0)=\varnothing\). There are no vertices to select, so the only vertex set is empty. It is independent and a clique, giving \(\alpha(K_0)=0\) and \(\omega(K_0)=0\). There are also no edges to leave uncovered, so the empty vertex set is a vertex cover and \(\tau(K_0)=0\). There can be no matching edge, hence \(\nu(K_0)=0\).
For an edge cover, select \(F=\varnothing\). Every vertex must be incident to an edge in \(F\); since there are no vertices, this requirement has no counterexample and is satisfied. Thus \(F\) is an edge cover, and no edge set can have fewer than zero edges, so \(\rho(K_0)=0\).
Check: the formulas give \(\lceil0/2\rceil=0\) and \(\lfloor0/2\rfloor=0\), agreeing with the direct counts. This is why the edge-cover formula includes \(n=0\).
Worked Example: The One-Vertex Graph \(K_1\)
Let \(V(K_1)=\{a\}\) and \(E(K_1)=\varnothing\). Its only nonempty vertex subset is \(\{a\}\), which is independent and a clique. Therefore \(\alpha(K_1)=1\) and \(\omega(K_1)=1\). Since there are no edges, the empty set of vertices is already a vertex cover, so \(\tau(K_1)=0\). There is no edge to select for a matching, giving \(\nu(K_1)=0\).
No edge cover exists: the vertex \(a\) would have to be incident to a selected edge, but \(E(K_1)\) is empty. Consequently \(\rho(K_1)\) is undefined, not zero.
Check: \(\lfloor1/2\rfloor=0\) agrees with the matching size, and the vertex-cover formula gives \(1-1=0\). The edge-cover formula is deliberately not applied at \(n=1\).
Worked Example: The Complete Graph \(K_4\)
Let \(V(K_4)=\{1,2,3,4\}\) and \(E(K_4)=\{12,13,14,23,24,34\}\). Every two vertices are adjacent, so an independent set has at most one vertex and a singleton attains this bound: \(\alpha(K_4)=1\). All four vertices form a clique, so \(\omega(K_4)=4\). A vertex cover needs at least \(4-1=3\) vertices, and any three vertices cover every edge, so \(\tau(K_4)=3\).
The edges \(12\) and \(34\) form a matching, so \(\nu(K_4)\ge2\). No matching can have more than \(\lfloor4/2\rfloor=2\) edges because each matching edge uses two distinct vertices; thus \(\nu(K_4)=2\). The same two edges cover all four vertices. Any edge cover needs at least \(\lceil4/2\rceil=2\) edges, since each edge touches at most two vertices, so \(\rho(K_4)=2\).
Check: the listed edge set has six edges. Independently, each vertex has degree three, so the sum of degrees is \(4\cdot3=12\); counting each edge at its two endpoints gives \(12/2=6\), as listed. The matching and edge cover each cover exactly four distinct vertices with two edges.
Worked Example: The Complete Graph \(K_5\)
Let \(V(K_5)=\{1,2,3,4,5\}\) and \(E(K_5)=\{12,13,14,15,23,24,25,34,35,45\}\). Every pair of distinct vertices is adjacent, so \(\alpha(K_5)=1\) and \(\omega(K_5)=5\). The vertex-cover formula gives \(\tau(K_5)=5-1=4\).
The two edges \(12\) and \(34\) form a matching. The upper bound is \(\lfloor5/2\rfloor=2\), so \(\nu(K_5)=2\); vertex \(5\) cannot be paired with another vertex in this matching. For an edge cover, select \(12,34,15\). These three edges cover vertices \(1,2,3,4,5\). At least \(\lceil5/2\rceil=3\) edges are necessary because two edges touch at most four vertices. Hence \(\rho(K_5)=3\).
Check: the edge list has ten entries. Independently, each of the five vertices has degree four, so the degree sum is \(5\cdot4=20\); dividing by two gives \(20/2=10\) edges. The edge cover uses three edges and includes every vertex, while two edges could cover at most \(2\cdot2=4\) vertices.
Common Pitfalls and Uses
Do not confuse an edge cover with a vertex cover. A vertex cover selects vertices and must touch every edge. An edge cover selects edges and must touch every vertex. For example, in \(K_4\), the minimum vertex cover has three vertices, whereas the minimum edge cover has two edges. These are different objects with different requirements.
Do not apply the edge-cover formula blindly. The statement \(\rho(K_n)=\lceil n/2\rceil\) is valid at \(n=0\) and for \(n\ge2\), but not as a defined parameter at \(n=1\). A tempting but incorrect calculation is to substitute \(n=1\), obtain \(\lceil1/2\rceil=1\), and claim that one edge covers the lone vertex. The correction is that \(K_1\) has no edges at all, so no edge cover exists. In contrast, \(K_0\) has an edge cover: the empty edge set covers every vertex because there are none.
The formulas are useful as exact benchmarks when checking definitions or testing a graph algorithm. In a complete graph, a largest independent set and a largest clique are determined immediately by adjacency; a largest matching pairs as many vertices as possible; and an edge cover pairs vertices, with one extra edge needed when the order is odd. Keeping the constructions alongside the bounds is important: a formula is justified not merely by showing that no better value is possible, but also by exhibiting a set that attains it.
Check Your Understanding
Use the definitions and prove each numerical claim from a bound and a construction where appropriate.
- For \(K_6\), find \(\alpha,\omega,\tau,\nu,\rho\). Give explicit matching and edge-cover edge sets.
- Explain why the empty set is an edge cover of \(K_0\), but no edge cover exists for \(K_1\).
- Prove directly that every vertex cover of \(K_n\), for \(n\ge1\), has at least \(n-1\) vertices.
- Give a matching of size \(\lfloor7/2\rfloor\) in \(K_7\), and identify the vertex not used by that matching.
- For \(K_5\), explain why two edges cannot be an edge cover, even though a matching of size two exists.