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

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$$.

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

But how can I prove this proposition formally?

• You cannot prove a property of all graphs by exhibiting a single graph. All your example shows is that $m(k+1)$ is tight, that is, there is a graph satisfying the given properties and having exactly $m(k+1)$ vertices. Dec 18, 2020 at 8:25
• I said the main idea is to show the maximum state is like the above graph. Please read my answer again. @YuvalFilmus Dec 18, 2020 at 9:02
• You need to show "if $G$ satisfies property $P$, then $G$ has at most $x$ vertices". What you're doing is "here is a graph $G_0$ satisfying property $P$ and having $x$ vertices". Sometimes you can deduce the former from the latter by showing how to transform every graph $G$ satisfying property $P$ to the graph $G_0$ without reducing the number of vertices. In this particular case, I'm not sure how to do that. In contrast, there is a very easy direct proof of your proposition. Dec 18, 2020 at 9:07

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)$$