Local Improvements in Extremal Arguments

Why Local Changes Reveal Structure

Many graph proofs begin by choosing an object that is best according to a stated measure: a smallest vertex cover, a largest independent set, or a minimum-weight spanning tree. Once such an object is fixed, consider a small change to it. If the change preserves feasibility and improves the measure, the chosen object could not have been optimal. This contradiction turns optimality into a structural condition.

The method has two parts. First, specify exactly which objects are feasible and what “best” means. Second, identify a permitted modification and compare the objective before and after it. The conclusion is usually a necessary condition for optimality, not automatically a characterization. A local change may rule out some candidates without proving that every candidate passing the test is globally optimal.

Finiteness matters: a nonempty finite feasible collection has an object attaining its minimum and an object attaining its maximum. In graph applications the collection might be all vertex covers, all independent sets, or all spanning trees of a fixed graph. The measure might be cardinality or total edge weight. A local-improvement proof does not need to construct every feasible object; it needs only a valid modification and a correct comparison.

What Optimality Forces for Vertex Covers

A vertex cover of a graph \(G=(V,E)\) is a set \(C\subseteq V\) containing at least one endpoint of every edge. A minimum vertex cover is one with the smallest cardinality among all vertex covers. We first derive a condition that holds at each of its vertices.

Proof. Fix \(v\in C\). Suppose that \(v\) has no neighbor outside \(C\). Then every neighbor of \(v\) belongs to \(C\setminus\{v\}\). Consider \(C'=C\setminus\{v\}\). An edge not incident with \(v\) is still covered by \(C'\), because its endpoints have not been removed from the cover. An edge incident with \(v\) has its other endpoint in \(C\setminus\{v\}\), by the supposition, so it too is covered by \(C'\). Thus \(C'\) is a vertex cover with \(|C'|=|C|-1\), contradicting the minimum cardinality of \(C\). Therefore \(v\) has a neighbor outside \(C\). \(\square\)

The argument proves only that some neighbor lies outside the cover. It does not say that this neighbor has no other neighbors in the cover. That stronger conclusion is not forced by minimum cardinality.

What Optimality Forces for Independent Sets

A set \(S\subseteq V\) is independent if no edge has both endpoints in \(S\). A maximum independent set has largest cardinality among all independent sets. The local change to consider is adding one vertex that is not already in the set.

Proof. Suppose that some \(v\in V\setminus S\) has no neighbor in \(S\). Since \(S\) is independent and no edge joins \(v\) to a vertex of \(S\), the set \(S\cup\{v\}\) is independent. Its cardinality is \(|S|+1\), contradicting that \(S\) has maximum cardinality. Thus every vertex outside \(S\) has a neighbor in \(S\). If \(V\setminus S\) is empty, the assertion has no vertices to check and holds vacuously. \(\square\)

This is a necessary condition: a maximum independent set cannot be enlarged by adding a single vertex. It does not assert that every independent set satisfying the condition is maximum. It says only that a particular type of improvement—adding one vertex without removing any—has been ruled out.

Edge Exchanges in Spanning Trees

A spanning tree of a connected graph is a subgraph containing every vertex that is connected and has no cycle. Suppose each edge \(e\) has a real weight \(w(e)\), and the weight of a spanning tree is the sum of the weights of its edges. A minimum spanning tree is a spanning tree of least total weight.

The local modification here exchanges edges: remove one edge from a spanning tree and insert another. The following condition is necessary for minimum total weight.

Proof. Fix an edge \(e=xy\notin E(T)\). Since \(T\) is connected, it contains an \(x\)-\(y\) path; since \(T\) has no cycle, that path is unique. Suppose that an edge \(f\) on the path has \(w(f)>w(e)\). Removing \(f\) from \(T\) separates \(T\) into two connected components: if it did not disconnect \(T\), another path between the endpoints of \(f\) would form a cycle with \(f\). The vertices \(x\) and \(y\) lie in different components, because the unique \(x\)-\(y\) path used \(f\). Adding \(e=xy\) therefore joins the two components. The resulting graph is connected and has no cycle, so it is a spanning tree. Its total weight is the weight of \(T\) minus \(w(f)\) plus \(w(e)\), which is strictly less than the weight of \(T\) because \(w(e)<w(f)\). This contradicts the minimum weight of \(T\). Hence every such \(f\) satisfies \(w(f)\le w(e)\). \(\square\)

The theorem is a necessary exchange condition. If it fails, the proposed tree is not minimum, because a specific improving exchange exists. The theorem alone does not claim that checking this condition proves minimum weight; a sufficient criterion would require a separate argument.

Common Mistake: Overstating What the Modification Proves

A local-improvement argument proves that a proposed optimum cannot admit a feasible improving move of the kind considered. The exact move matters. For a vertex cover, the deletion test proves that each cover vertex has at least one neighbor outside the cover. It does not prove that the neighbor is adjacent to no other cover vertex.

For a concrete counterexample to that stronger claim, let \(G=K_3\), with \(V=\{1,2,3\}\) and \(E=\{12,23,13\}\). The set \(C=\{1,2\}\) is a minimum vertex cover: each of the three edges is incident with \(1\) or \(2\), and a single vertex cannot cover all three edges because the edge joining the other two vertices would be uncovered. For \(v=1\), the outside neighbor is \(3\), but \(3\) is also adjacent to \(2\in C\). In set notation, \(N(3)\cap C=\{1,2\}\), not \(\{1\}\). Thus this minimum cover does not give \(1\) a neighbor outside the cover whose only neighbor in the cover is \(1\).

The correct conclusion remains true: \(1\) has a neighbor outside \(C\), namely \(3\), and \(2\) also has the outside neighbor \(3\). In general, removing a cover vertex is justified only when all its incident edges remain covered by other vertices; the proposition establishes that this cannot happen for a vertex in a minimum cover. It does not establish any stronger uniqueness property for the outside neighbor.

When using the method, state the modification before drawing the conclusion. “No vertex can be added” is weaker than “no set of vertices can replace some of the current set.” “No single edge exchange improves the tree” is weaker than a proof that every other spanning tree has at least its weight. Matching the claim to the modification is what keeps an extremal proof valid.