Prove that $β_0(G) ≥ δ(G)$ for any graph $G$, where $δ(G)$ denotes the minimal vertex degree in the graph and $β_0(G)$ is the minimum covering. Find a graph for which the equality holds.
A hint is given and I have tried to use follow it but, I couldn't get it. The is it below:
Hint: Consider a vertex $v$ of degree $0$. Prove that a covering of edges
incident to the vertex set $v \cup N(v)$ contains at least $0$ vertices.
Kindly help me out!
You can use induction on the number of vertices. For an empty graph the statement is trivial. Now let $G$ be a graph and $v$ be a minimum degree vertex. A vertex cover contains either $v$ or every neighbour of $v$ (why?). In the latter case it has at least $\delta(G)$ vertices. In the former case, deleting $v$ from the vertex cover gives a vertex cover of $G-v$. The minimum degree of $G-v$ is at least $\delta(G) - 1$, since the degree of every vertex apart from $v$ decreased by at most one. It follows by the induction hypothesis that a vertex cover of $G-v$ has size at least $\delta(G) - 1$, so after adding $v$ back in, it has size at least $\delta(G)$.