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

  • 1
    $\begingroup$ 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? $\endgroup$ – M. Vinay Nov 23 '19 at 16:53
  • $\begingroup$ 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? $\endgroup$ – jonan Nov 23 '19 at 16:56
  • 1
    $\begingroup$ 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]. $\endgroup$ – M. Vinay Nov 25 '19 at 7:02
  • $\begingroup$ @M.Vinay i've added something below. Let me know what you think. $\endgroup$ – 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.

  • 1
    $\begingroup$ 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. $\endgroup$ – M. Vinay Nov 28 '19 at 10:00
  • 1
    $\begingroup$ @M.Vinay thanks! Perhaps I should clarify a bit more. If n is 0 or 2 (mod 3), then we only need to contract the edge from v to w, and apply induction hypothesis to this new graph. The minor produced in both of those cases suffices. Else, if n is 3k + 1, we have to make the two contractions as described above, then the real trick is to use the induction hypothesis on the neighbour set of x. This gives us a minor of size k, but then x is attached to its neighbour set so we can ensure a minor of size k+1, then this suffices. $\endgroup$ – jonan Nov 28 '19 at 15:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.