A maximal matching gives a 2-approximate minimum vertex cover

Consider the following deterministic procedure: list the edges of $G$ in the fixed order, start with $M=\mathrm{\varnothing }$, and scan the list once, adding the current edge to $M$ when neither of its endpoints is already $M$-saturated; at the end return $M$ and the set $C$ of all endpoints of edges of $M$. Each step inspects two saturation marks and possibly sets two of them, so the procedure runs in time polynomial in the encoded size of $G$, and the fixed edge order is its tie rule.

One has $\mathrm{\mid }M\mathrm{\mid }\le {\mathrm{OPT}}_{\mathrm{V}\mathrm{C}}$. Let $C^{\ast }$ be a vertex cover with $\mathrm{\mid }{C}^{\ast }\mathrm{\mid }={\mathrm{OPT}}_{\mathrm{V}\mathrm{C}}$. Each edge of $M$ has at least one endpoint in $C^{\ast }$; assign to it such an endpoint explicitly: the smaller of its two endpoints in the fixed vertex order if that endpoint lies in $C^{\ast }$, and otherwise its other endpoint. Distinct edges of $M$ are vertex-disjoint, so distinct edges receive distinct vertices of $C^{\ast }$; the assignment is therefore an injection of $M$ into $C^{\ast }$, and $\mathrm{\mid }M\mathrm{\mid }\le \mathrm{\mid }{C}^{\ast }\mathrm{\mid }={\mathrm{OPT}}_{\mathrm{V}\mathrm{C}}$.

Since $M$ is a matching, its edges are pairwise disjoint, so the $2\mathrm{\mid }M\mathrm{\mid }$ endpoints of its edges are distinct vertices and $\mathrm{\mid }C\mathrm{\mid }=2\mathrm{\mid }M\mathrm{\mid }$. Every vertex of $C$ is $M$-saturated by construction.

The matching $M$ is maximal. Indeed, suppose an edge $e$ of $G$ had both endpoints not in $C$, that is, both $M$-exposed at the end of the scan. A vertex once marked saturated is never unmarked, so both endpoints were still exposed when $e$ was scanned; the procedure would then have added $e$ to $M$, a contradiction. Hence no edge can be added to $M$, and $M$ is maximal.

If $G$ has no edges, the scan adds nothing, so $M=\mathrm{\varnothing }$ and $C=\mathrm{\varnothing }$; the empty set is a vertex cover and no nonempty set is needed, so ${\mathrm{OPT}}_{\mathrm{V}\mathrm{C}}=0=\mathrm{\mid }C\mathrm{\mid }=2\mathrm{\mid }M\mathrm{\mid }$, and both sides of the displayed bound are zero.

The set $C$ is a vertex cover: if some edge $e$ of $G$ had both endpoints outside $C$, then $M\cup \{e\}$ would be a matching strictly larger than $M$, contradicting maximality. Hence every edge meets $C$, so $C$ is a vertex cover and ${\mathrm{OPT}}_{\mathrm{V}\mathrm{C}}\le \mathrm{\mid }C\mathrm{\mid }$.

Combining steps 2.1, 3.1 and 1.2, $\mathrm{\mid }C\mathrm{\mid }=2\mathrm{\mid }M\mathrm{\mid }\le 2{\mathrm{OPT}}_{\mathrm{V}\mathrm{C}}$ and $C$ is a vertex cover computed by the deterministic polynomial-time procedure of step 1.1. By [F4] the procedure is a $2$-approximation for the minimum vertex cover problem.

For every finite simple graph, a maximal matching is produced in deterministic polynomial time after the tie rule of step 1.1 is fixed, its endpoint set is a vertex cover $C$ with $\mathrm{\mid }C\mathrm{\mid }=2\mathrm{\mid }M\mathrm{\mid }\le 2{\mathrm{OPT}}_{\mathrm{V}\mathrm{C}}$, and the edgeless case is covered by step 2.3.