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.

enter image description here

But how can I prove this proposition formally?

Thank you in advance for your answers.

  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Dec 18 '20 at 8:25
  • $\begingroup$ I said the main idea is to show the maximum state is like the above graph. Please read my answer again. @YuvalFilmus $\endgroup$ – Sepehr Omidvar Dec 18 '20 at 9:02
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Dec 18 '20 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)$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.