Let $G=(V,E)$ be a finite, simple, undirected graph. A *matching* is a set $M\subseteq E$ of pairwise disjoint edges. A *vertex cover* is a set $C\subseteq V$ of vertices such that $C\cap e \neq \emptyset$ for all $e\in E$.


The *matching number* $\mu(G)$ of $G$ is the maximum size that a matching can have, and the *vertex cover number* $\tau(G)$ is the minimum size that a vertex cover can have.


If $M$ is a maximal matching with respect to $\subseteq$, then $C=\bigcup M$ is a vertex cover by maximality of $M$, and $|C|=2|M|$, so we have $\tau(G)\leq 2\cdot \mu(G)$ for all graphs $G$.


**Question.** What is the value of $$\inf\{c\in \mathbb{R}: \tau(G)\leq c\cdot \mu(G) \text{ for all finite graphs } G\}?$$



Vertex cover number vs matching number
Minimum $c$ equals 2 as is seen from the complete graph on a large number $n$ of vertices: $\tau$ equals $n-1$, $\mu$ equals $[n/2]$.


