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?

exactly$M-m$, since the $2m+1$ from the clique contains at most one vertex from any independent set. $\endgroup$ – Tony Huynh Mar 13 '13 at 5:34