MathOverflow is a question and answer site for professional mathematicians. 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

Let $G$ be a graph on an even number of vertices, say $2M$. Assume that the largest independent set in $G$ has at most $M$ elements. Is it true that there exists a set of $2m$ vertices (for some $m\leq M$), say $v_1,v_2,\ldots, v_{2m}$, with the following three properties:

1) The induced subgraph on $v_1,\ldots,v_{m-1}$ is an independent set;

2) The induced subgraph on $v_m,\ldots,v_{2m}$ is a clique;

3) Removing these $2m$ vertices from $G$ leaves a graph with no independent set larger than M-m.

It turned out that the claim is not true and Colin provided a counterexample - a cycle on five vertices and an isolated vertex.

A less precise question. Under the same condition - a graph $G$ on $2M$ vertices with no independent set larger than $M$ - could we say something about the structure of $G$ like:

a) $G$ is has a very particular form (say an independent set on $M-1$ vertices and a clique on $M+1$ vertices);

b) Otherwise we can partition the vertex set of into part with even number of vertices (say $2m_i$) so that the induced subgraphs on these sets of vertices have each no independent set larger than $m_i$?

Comment: If we could have such a statement, maybe we could say something more about these small graphs? That is, maybe they could have a very simple structure like a cycle on an odd number of vertices and an isolated edge?

share|cite|improve this question
You say $M=3$ works - what about a cycle of length $5$ + one isolated vertex? – Colin McQuillan Mar 12 '13 at 11:00
Colin, then take $m=1$ and remove two vertices, one of which is the isolated vertex. – Andrew D. King Mar 12 '13 at 18:44
(I am assuming TOM means $v_1,\ldots, v_m$ are a stable set and $v_{m+1},\ldots,v_{2m}$ are a clique. Is that the case?) – Andrew D. King Mar 12 '13 at 19:00
In that case, doesn't Colin provide a valid counterexample? – Andrew D. King Mar 13 '13 at 5:26
Dear TOM. It seems to me that the current statement is not weaker than the original one. That is, if the current statement is true, then by induction on $M$, the original statement is true. Note that condition (3) is equivalent to saying that the after removing these $2m$ vertices we get a graph with independence number exactly $M-m$, since the $2m+1$ from the clique contains at most one vertex from any independent set. – Tony Huynh Mar 13 '13 at 5:34

Your Answer


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

Browse other questions tagged or ask your own question.