Recall that a vertex cover of a graph is a set of vertices such that every edge of the graph is incident to at least one vertex in the set. How does this definition relate to the concept of an approximation algorithm?

Consider the relationship between matchings and vertex covers in a graph. How can a maximal matching be used to construct a vertex cover, and what does this imply about the size of the cover compared to the matching?

Prove that any maximal matching in a graph has a size that is at least half the size of any vertex cover. Use this to derive the 2-approximation ratio for the algorithm that selects both endpoints of every edge in a maximal matching as the vertex cover.