# clique, independent set, and minimum vertex cover

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

• (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.
• 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? – Karolis Juodelė Dec 6 '13 at 18:51
• 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$ – flashburn Dec 6 '13 at 19:09