Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 2 down vote accepted

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

share|cite|improve this answer
That sounds a whole lot simpler than my rationale. – raphnguyen Sep 5 '11 at 23:05
This is only true for connected graphs. – Paulpro Oct 17 '12 at 21:18
Actually, it applies to disconnected graphs as well, provided the graph has no isolated vertices. – Doc Nov 9 '13 at 17:00

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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