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

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

• It looks like you're trying to prove that $G$ contains $K_{\lceil \frac n 3\rceil}$ as a subgraph, and not merely as a minor. Or did I miss something? – M. Vinay Nov 23 '19 at 16:53
• You are right. I am not so comfortable working with minors yet. Do you see a way for me to modify this argument to take this into account? – jonan Nov 23 '19 at 16:56
• Sorry, I still don't have a solution, but I did get some ideas. If $G$ is not complete, then consider any two non-adjacent vertices $u$ and $v$ of $G$. If you can find such a non-adjacent pair that have no common neighbours, then the closed neighbourhood of at least one of them must be a complete graph of order greater than or equal to $\lceil \frac n 3 \rceil$ (for the neighbourhood of each is exactly the set of non-neighbours of the other). On the other hand, if any two non-adjacent vertices have at least one common neighbour, then this is some special graph [but I'm unable to proceed]. – M. Vinay Nov 25 '19 at 7:02
• @M.Vinay i've added something below. Let me know what you think. – jonan Nov 27 '19 at 3:00

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.
• Very nice! I came close, but for some reason didn't think of using induction — I thought some counting argument could show that we could contract some $k$ edges to get the minor, but couldn't figure out which edges and how many. – M. Vinay Nov 28 '19 at 10:00