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?
Best Answer
In a connected graph, every vertex cover is a dominating set, so the smallest dominating set cannot be bigger than the smallest vertex cover.