I was given a graph problem with 3 different questions and 1 set of answers. The problem is described below. The problem that I'm having is that it seems to me that the answer to all the questions is the same. I keep trying to find a caveat but I don't see one. What am I missing?

Here is the problem

Undirected graph $G$. $n$ - number of vertices. $m$ - number of edges. $d$ - maximum degree of a graph.

  1. The maximum clique size of $G$ is no larger than
  2. The minimum vertex cover size of $G$ is no larger than
  3. The maximum independent set size of $\overline{G}$, the complement of $G$, is no larger than

Set of answers

  • (a) $d+1$
  • (b) $n$
  • (c) $n-1$
  • (d) $n/2$
  • (e) $d$
  • (f) $n-d$

It looks to me that the answer to every problem is (b) $n$, because

  1. Clique cannot have more vertices than there are in a graph
  2. Vertex cover cannot be larger than the number of vertices in a graph
  3. Maximum independent set cannot be larger than the number of vertices in a graph.

I feel like I'm missing something, because the answers seem too obvious.

Any help is appreciated


Of course, $n$ being the largest of the given answers will satisfy all conditions. You are expected to find the least upper bounds though.

  • $\begingroup$ This is where I'm stuck then. How would I even start reasoning about this problem? $\endgroup$
    – flashburn
    Dec 6 '13 at 18:46
  • $\begingroup$ First, You know that there exist graphs, for which $n$ is the exact solution, so you have to think about $d$. Think of some graphs that can't have a cover of $n$. What do they have in common? $\endgroup$ Dec 6 '13 at 18:51
  • $\begingroup$ I'm at a loss. What could the graphs that don't have a cover of $n$ have in common? The only thing I can think of is that total degree of a graph is equal the double count of edges, i.e. $d=2m$ $\endgroup$
    – flashburn
    Dec 6 '13 at 19:09
  • $\begingroup$ What I was aiming for was an edge. $\endgroup$ Dec 6 '13 at 19:26
  • $\begingroup$ I feel really stupid, because I still don't see it. What do edges give me, how are they related to the set of answers that has been given go me? $\endgroup$
    – flashburn
    Dec 6 '13 at 19:37

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.