Number of vertices of a graph in vertex cover of size $m$

Question

Let $G$ have a vertex cover of size at most $m$ and let the degree of $G$ be bounded by $k$. Then $G$ has at most $m(k+1)$ vertices.

Note: Remove all vertices of degree $0$.

---

Answer:

The idea is to have $m$ graphs like the below one.

But how can I prove this proposition formally?

Thank you in advance for your answers.

Answer 1

Consider the graph $G=(V, E)$, where each vertex in $G$ has at most $k$ neighbours. Let $C\subseteq V$ be a vertex cover of size at most $m$. For a vertex $v\in C$, let $c(v) = \{v\} \cup \{ u\in V: \{u, v \}\in E\}$, that is, $c(v)$ is the set of vertices that are covered by the vertex $v$ (including $v$ itself).

A side note: the subgraph induced by the vertices in $c(v)$, for any $v$, is a "star" graph (similar to the one you attached, yet the number of vertices that are neighbours of $v$ in this subgraph can be strictly less than $k$). The idea is to consider star graphs corresponding to the vertices in $C$, and then use the union bound for sets.

Now $C$ being a vertex cover implies that $\bigcup\limits_{v\in C} c(v) = V$. This is easy, yet we prove it for completentss: the $\subseteq$-containment is trivial. The other direction follows as for every vertex $v\in V$, one of the following holds:

• $v\in C$: in this case, as $v\in c(v)$, we have that $v\in \bigcup\limits_{v\in C} c(v)$.
• there is $u\in C$ such that $\{u, v\}\in E$: in this case, as $v\in c(u)$, we have that $v\in \bigcup\limits_{v\in C} c(v)$.

Finally, the following holds $$ |V| = |\bigcup\limits_{v\in C} c(v)| \leq \sum\limits_{v\in C} |c(v)| \leq |C|\cdot max_{v\in C} (|c(v)|) \\\leq |C|\cdot max_{v\in C}(degree(v) + 1) \leq |C|\cdot (k + 1) \leq m\cdot(k+1)$$