= Vertex cover number
{title2=$\tau(G)$}
The <vertex cover number> records the size of a <minimum vertex cover>:
$$
\tau(G)=\min\{|C|:C\subseteq V(G),\ C\text{ is a vertex cover of }G\}.
$$
The <vertex cover number> is a number, while a <minimum vertex cover> is a <set> attaining it. For the <cycle graph> $C_5$, the <independence number> is $2$, so the complement correspondence gives $\tau(C_5)=5-2=3$. The <vertex cover> $\{1,3,4\}$ above attains this size.
Every <matching in a graph> gives a lower bound on the <vertex cover number>. Its <edges> have no shared endpoints, so covering each selected <edge> requires a different <vertex>. Thus, for any <matching in a graph> $M$ and any <vertex cover> $C$,
$$
|M|\leq |C|,\qquad \nu(G)\leq\tau(G),
$$
where $\nu(G)$ is the <matching number>. Exhibiting a <matching in a graph> and a <vertex cover> of the same size certifies that both are optimum. <Kőnig's theorem for bipartite matching> says that every finite <bipartite graph> admits this equality: $\nu(G)=\tau(G)$.<Graph Theory by Reinhard Diestel>[Diestel, Graph Theory, Section 2.1, Theorem 2.1.1 and its lower-bound argument]{ref}
For the <complete bipartite graph> $K_{2,3}$, let the left <vertices> be $L=\{a,b\}$ and the right <vertices> be $R=\{x,y,z\}$. All six <edges> join $L$ to $R$. Selecting $C=L$ covers every <edge>; selecting $M=\{ax,by\}$ gives a <matching in a graph> of size two. The lower bound and this <vertex cover> give $2\leq\tau(K_{2,3})\leq2$, so $\tau(K_{2,3})=\nu(K_{2,3})=2$. The remaining <vertices> $R$ form a largest <independent set> of size three. Crossings of drawn <edges> are not extra <vertices>.
\Image[/bipartite-matching-cover-certificate.png]
{title=Two disjoint matching edges certify that the two left vertices are a minimum cover of K₂,₃}
The <bipartite graph> hypothesis matters. In a <triangle in a graph>, any two <vertices> form a <minimum vertex cover>, while any two <edges> share an endpoint. Hence $\tau(K_3)=2$ and $\nu(K_3)=1$. Similarly, the <cycle graph> $C_5$ has $\tau(C_5)=3$ and $\nu(C_5)=2$. The inequality for the <matching number> remains valid, but equality can fail.
Back to article page
