Certificates for Covers, Independent Sets, and Cliques

Three Kinds of Set Certificates

Many graph questions ask whether a proposed set has a particular property: does it meet every edge, contain no adjacent vertices, or consist entirely of mutually adjacent vertices? These properties can be verified by inspecting the graph’s edges and nonedges. A proposed set with a verified property is a certificate of feasibility: it proves that the set works. By itself, it does not prove that the set is smallest or largest among all sets with that property.

Throughout, graphs are finite and simple. Thus an edge joins two distinct vertices, and there is at most one edge between any pair. For distinct vertices \(u,v\), the pair \(uv\) is a nonedge when \(uv\notin E(G)\). All the checks below concern pairs of distinct vertices; a vertex is not paired with itself.

The three tests have different directions. To check a cover, inspect the edges of the graph. To check an independent set, inspect pairs within the proposed set and make sure none is an edge. To check a clique, inspect pairs within the proposed set and make sure each one is an edge. A single uncovered edge, internal edge in an independent set, or missing edge in a clique is enough to reject a proposed certificate.

Why the Checks Work

Proof. First consider the cover statement. If \(C\) is a vertex cover, take any two distinct vertices \(u,v\in V(G)\setminus C\). If \(uv\) were an edge, neither endpoint would belong to \(C\), contradicting that \(C\) meets every edge. Thus \(V(G)\setminus C\) is independent. Conversely, suppose \(V(G)\setminus C\) is independent. If an edge had neither endpoint in \(C\), both endpoints would belong to \(V(G)\setminus C\), contradicting independence. Therefore every edge has an endpoint in \(C\), so \(C\) is a vertex cover.

For the complement statement, the complement \(\overline G\) has the same vertex set as \(G\), and two distinct vertices are adjacent in \(\overline G\) exactly when they are nonadjacent in \(G\). If \(Q\) is a clique in \(G\), every pair in \(Q\) is an edge of \(G\), hence a nonedge of \(\overline G\); so \(Q\) is independent in \(\overline G\). Conversely, if \(Q\) is independent in \(\overline G\), none of its pairs is an edge of \(\overline G\), so every pair is an edge of \(G\). Hence \(Q\) is a clique in \(G\). \(\square\)

These equivalences explain why all three certificates reduce to pair checks. A cover can be checked either by looking for an edge with both endpoints outside the proposed cover, or by checking that the omitted vertices form an independent set. A clique can be checked in \(G\), or by checking that the same vertices form an independent set in \(\overline G\).

Proof. For the cover test, inspect every edge \(uv\in E(G)\) and accept exactly when \(u\in S\) or \(v\in S\) for each edge. This is precisely the definition of a vertex cover, so the test accepts exactly the covers. For the independent-set test, inspect every pair of distinct vertices \(u,v\in S\) and accept exactly when \(uv\notin E(G)\) for each pair. This is precisely the definition of independence. For the clique test, inspect every pair of distinct vertices \(u,v\in S\) and accept exactly when \(uv\in E(G)\) for each pair. This is precisely the definition of a clique. If there are no edges to inspect, the cover test accepts: the empty edge set is met by every set. If there are fewer than two vertices in \(S\), there are no pairs to inspect, so both pair tests accept, as required by their definitions. \(\square\)

For an explicit check, one may mark the vertices of \(S\) and scan the edge list for a cover, or list all pairs in \(S\) for an independent set or clique. If \(S\) has \(k\) vertices, there are \(k(k-1)/2\) distinct pairs to test. A pair can appear only once in this list, since the graph is simple and the pair is unordered. For an independent set, one can stop as soon as an internal edge is found; for a clique, one can stop as soon as a required edge is missing.

Worked Certificates in One Graph

This example also illustrates that one vertex set can have different roles in a graph. Here \(\{2,3,4\}\) is both a cover and a clique, but these claims need different checks: the cover claim concerns every edge of \(G\), while the clique claim concerns only the pairs inside \(\{2,3,4\}\). Checking that the three internal pairs are edges does not by itself establish that the set covers all edges.

Rejecting Plausible but Invalid Certificates

For a cover, it is important to scan every edge, not just edges incident with a particular vertex or a chosen part of the graph. For an independent set or clique, it is important to check every pair in the proposed set, not merely consecutive vertices in some ordering of that set. Their definitions impose conditions on all relevant edges or pairs.

What a Valid Certificate Does—and Does Not—Prove

There is a useful distinction between verifying a set’s property and optimizing its size. Write \(\tau(G)\) for the minimum size of a vertex cover, \(\alpha(G)\) for the maximum size of an independent set, and \(\omega(G)\) for the maximum size of a clique. If a proposed set \(C\) is a verified cover, its size gives an upper bound \(\tau(G)\leq |C|\). If \(I\) is a verified independent set, then \(\alpha(G)\geq |I|\). If \(Q\) is a verified clique, then \(\omega(G)\geq |Q|\). These bounds follow directly from the meanings of minimum and maximum: the minimum cannot exceed the size of one available cover, and the maximum cannot be smaller than the size of one available independent set or clique.

None of those one-sided bounds alone proves optimality. A cover of size \(4\) proves that a cover of size at most \(4\) exists; it does not rule out a cover of size \(3\). A clique of size \(3\) proves that a three-vertex clique exists; it does not rule out a larger clique elsewhere in the graph. To establish optimality, an argument must also rule out all better candidates, usually by providing a separate bound or proof. The edge and pair checks establish feasibility, not that no competing set is better.

Likewise, maximal and maximum describe different claims. A maximal independent set cannot be enlarged by adding a vertex while keeping it independent; a maximum independent set has the largest size among all independent sets. Direct pair checks can verify independence, and one can test whether a particular outside vertex can be added, but neither test by itself compares the set with every independent set in the graph. A valid certificate for membership in one of these families should not be mistaken for a certificate of optimal size.

A Reliable Checking Routine

The routine also handles boundary cases. The empty set is a cover of an edgeless graph because there are no edges that fail the condition. The empty set and every one-vertex set are independent sets and cliques: there are no pairs of distinct vertices within them to violate either condition. These conclusions follow from the definitions and the universal checks in the verification proposition.

Thinking of a proposed set as a certificate makes a graph claim concrete and auditable. A cover is supported by an edge-by-edge check; independence and clique claims are supported by a pair-by-pair check. If a claim fails, a single counterexample identifies the failure. If it passes, the certificate confirms the stated property—but any claim of minimum or maximum size still requires a further argument.