Worked certificate and reduction examples

A four-cycle

Edges are (0,1),(1,2),(2,3),(3,0). Set {0,2} covers all edges; {1,3} is its independent complement. Matching {(0,1),(2,3)} has two edges, so any cover needs at least two vertices. The feasible size-two cover meets this lower bound and is therefore optimal. Selecting both endpoints of the matching instead gives all four vertices: feasible, within factor two, but nonoptimal.

A triangle

Any two vertices cover the triangle, and no single vertex does. A matching has only one edge, so the matching lower bound of one is valid but not tight. Exact enumeration proves OPT=2. Never claim the lower bound must equal optimum on nonbipartite graphs.

The threshold transformation

For a graph with five vertices and Independent Set threshold k=3, ask Vertex Cover with budget 2 on the same graph. A size-at-least-three independent set has a complement of size-at-most-two covering all edges; a cover of size-at-most-two leaves at least three independent vertices. The inequalities matter when solutions are larger or smaller than the threshold.

A weighted counterexample

On a single edge, vertex weights 100 and 1 make taking both cost 101 while optimum is 1. The cardinality proof |C|=2|M| says nothing about a weighted objective. A changed objective requires a new algorithm/proof, not just replacing the displayed count by a sum.