I am working on a proof for the following description:

Let D and C be a minimum dominating set and a minimum vertex cover of a connected graph G, respectively. Prove that $|D| \leq |C|$.

My thinking is that when looking for a dominating set, you can start from a vertex (let's call it A), follow it to the next vertex (B), and then any adjacent vertex (C) to that vertex. So in reality, this would cover edges AB and BC. However when looking for a minimum vertex cover, you can only cover an edge adjacent to your beginning vertex. In this instance, if we started at vertex B, it would cover both edges AB and BC. However, if there were more vertices adjacent to A, then vertex B would not be the ideal starting point when looking for a minimum vertex cover. Therefore, |D| will always be less than or equal to |C|.

Is this the correct way of looking at this? How can I simplify my thoughts into a conclusive generalized statement?


1 Answer 1


In a connected graph, every vertex cover is a dominating set, so the smallest dominating set cannot be bigger than the smallest vertex cover.

  • $\begingroup$ That sounds a whole lot simpler than my rationale. $\endgroup$
    – raphnguyen
    Commented Sep 5, 2011 at 23:05
  • 1
    $\begingroup$ This is only true for connected graphs. $\endgroup$
    – Paul
    Commented Oct 17, 2012 at 21:18
  • $\begingroup$ Actually, it applies to disconnected graphs as well, provided the graph has no isolated vertices. $\endgroup$
    – Doc
    Commented Nov 9, 2013 at 17:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .