Show $\alpha(G) \leq 2$ implies G contains $K_{\left \lceil \frac{n}{3} \right \rceil}$ as a minor

Question

G is simple. I want to show $\alpha(G) \leq 2$ implies G contains $K_{\left \lceil \frac{n}{3} \right \rceil}$ as a minor.

This is what I have so far:

If $\alpha(G) = 1$, the graph $G$ is complete and it must contain the desired minor. So we assume $\alpha(G) = 2$, thus for any choice of three vertices in $G$, there must be at least one edge between the three. Thus, the compliment of $G$, denoted $G^c$, cannot contain $K_3$ as a subgraph.

Notice that if there exists some vertex $v$ in $G^c$ with $\deg(v) = t$, then if we look at the neighbours of $v$, there cannot be any edges between the neighbours, (by the fact that no $K_3$ subgraph in $G^c$), so we have an independent set of size $t$ in $G^c$. Equivalently, we have a $K_t$ subgraph in $G$.

So it suffices to show that $G^c$ contains some vertex $v$ with $\deg(v) \geq {\left\lceil \frac{n}{3} \right \rceil}$

or equivalently, that $G$ contains some vertex $v$ with $\deg(v) \leq n - {\left\lceil \frac{n}{3} \right \rceil} = {\left \lfloor \frac{2n}{3} \right \rfloor}$

Suppose it did not contain such a vertex, then for all vertices $v$ in $G$, we have that: $\deg{v} \geq {\left\lceil \frac{2n}{3} \right \rceil}$

I know that, from here, I can look at a vertex in G and it's $ {\left\lceil \frac{2n}{3} \right \rceil}$ neighbours, and use the fact that the largest independent set is 2 to show that there are many edges between the neighbours of v. It seems like this "connectedness" should either give a subgraph of size at least $ {\left\lceil \frac{n}{3} \right \rceil}$, or contradict the independent set condition. However, I am unsure how to proceed. Any help/advice would be appreciated. Thanks

Answer 1

We will prove by induction. If $n \leq 3$, then it is trivial. Now, if $G$ is complete, we are done. So suppose not, then there exists some vertices $u$ and $v$ not adjacent to eachother. Then by condition on independent sets, every vertex in $G - u - v$ is adjacent to atleast one of $u$ and $v$. Thus, we can "partition" the vertices of $G - u - v$ in the following way: denote by $A$ the vertex set containing vertices only connected to $u$, denote by $B$ the vertex set of vertices connected to $u$ and $v$, and denote by $C$ the vertex set of vertices connected only to $v$.

Suppose two vertices in $A$ are non-adjacent, then they form an independent set of size 3 with $v$, contradicting independence condition. Thus $A$ is a complete subgraph. The same is true for $C$ with $u$. Thus we certainly have a minor of size $|A| + 1$ and $|C| + 1$ $(*)$, the plus one coming from $u$ and $v$ respectively.

Finally, since $|A| + |B| + |C| + 2 = n$, then one of these three vertex sets has size $ \geq \left \lceil \frac{n-2}{3} \right \rceil $. If this holds for $A$ or $C$, we are done by $(*)$ above.

If it is $B$, then, in particular, $B$ is non-empty. So there exists a vertex in $B$, called $w$, which is adjacent to $u$ and $v$. Contract the edge from $u$ to $w$, then contract the edge from this merged vertex to $v$, then we have some new vertex $x$ which is adjacent to everything in $A$, $B$ and $C$. Thus in this new graph $G'$, we have $n-2$ vertices, and since contracting edges could not have increased the size of the maximum independent set, we can apply the induction hypothesis to $G'$, so there exists a $K_{\left \lceil \frac{n-2}{3} \right \rceil }$ minor in this new graph, which corresponds to a $K_{\left \lceil \frac{n-2}{3} \right \rceil + 1}$ minor in the original graph G, (since one of $u$, $v$ or $w$ is in the minor), and since $\left \lceil \frac{n-2}{3} \right \rceil + 1 \geq \left \lceil \frac{n}{3} \right \rceil $, we are done.