The following approximation algorithm determines a cover that is close to minimal size:
\textbf{Data}: a list L of pairs \{u, v\} of people who know each other
\textbf{Result}: a cover that is close to minimal size
S \leftarrow \emptyset
\textbf{for} \{u, v\} \in L \textbf{do}
\quad \textbf{if} u, v \notin S \textbf{then}
\quad \quad randomly choose u or v with equal probability
\quad \quad add the chosen vertex to S
\quad \textbf{end}
\textbf{end}
\textbf{return} S
Prove that this algorithm indeed returns a cover.