3
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
12
  • $\begingroup$ This is where I'm stuck then. How would I even start reasoning about this problem? $\endgroup$
    – flashburn
    Commented Dec 6, 2013 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$
    – Karolis Juodelė
    Commented Dec 6, 2013 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
    Commented Dec 6, 2013 at 19:09
  • $\begingroup$ What I was aiming for was an edge. $\endgroup$
    – Karolis Juodelė
    Commented Dec 6, 2013 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
    Commented Dec 6, 2013 at 19:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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