Graph theory: proving that a graph with specific property is bipartite

Question

I have been given the following problem on an exercise sheet:

Let $G$ be a graph with $n$ vertices with the property that for each $k ≤ n$, every set of $k$ vertices contains a subset of size at least $k/2$ with no edges inside it.

Prove that $G$ is a bipartite graph.

I am struggling to see a way to construct this proof. I have tried to use that a graph is bipartite if and only if it contains no odd cycles, but I think I'm incorrect in doing so as I seem to be going in circles. Any help would be appreciated.

Answer 1

You were on the right track. Here is a hint: try proving the contrapositive. Let $G$ be a graph that is not bipartite. You want to show that there exists a set of $k$ vertices with no independent subset of size at least $\frac{k}{2}$.

As you know, if $G$ is not bipartite, then there is an odd cycle, say of length $k=2m+1$. So...