Let $G$ be a triangle-free graph. Let $n_{0} = v(G)$. Now $G$ will have a an independent set of size $\lfloor \sqrt{n_{0}} \rfloor$. You can google wikipedia on triangle-free graph and you will get the proof.
What I would like to do is this. Remove the above independent set, call it $S$. Now $G – S$ is also triangle free. Let $n_{1} = v(G-S)$. Do the same thing, i.e removing an independent set of size $\lfloor \sqrt{n_{1}} \rfloor$.
Repeat the process until we have $0$ vertices left.
Clearly, if $v(G) \geq 1$, the operation will remove a positive number of nodes, until there are $0$ nodes left.
Question is, how do I prove the number of steps, until termination, is $ \leq 2 \lceil \sqrt{n_{0}} \rceil$?
I tried induction, but it fails. Consider $n = 625$. Then $625 – \lfloor \sqrt{625} \rfloor = 600$. Suppose the proposition is true for all $n < 625$. But $2 \lceil \sqrt{600} \rceil = 50$. So I cannot prove this by showing $2 \lceil \sqrt{n – \lfloor \sqrt{n} \rfloor} \rceil + 1 \leq 2 \lceil \sqrt{n} \rceil$.
If we add $1$, the result will be $51$, but $2 \lceil \sqrt{625} \rceil = 50$.
I wrote C++ code to simulate this recursive function, and for $n \leq 1000000$, this result holds. Can anyone prove this for me? I am quite stuck. This question is for a class on graph theory, and as a computer science student, I don't really have any tricks to handle math problems with floors and ceilings. Really just want to give up and tell my math teacher prove by test cases haha.
Best Answer
Let $f(n)$ be the maximum number of steps until termination when there are $n$ vertices. We want to show that $f(n)\le 2\lceil\sqrt{n}\rceil$, and we are given that $f(n)\le 1+f(n-\lfloor\sqrt{n}\rfloor)$, since we can just remove the set of size $\lfloor\sqrt{n}\rfloor$. We have $f(0)=0, f(1)=1$.
This is a bit bashy, but we can find something a bit stronger. Specifically, we can say $f(n)\le \lfloor\sqrt{4n-3}\rfloor\le\lfloor\sqrt{4n}\rfloor=\lfloor2\sqrt{n}\rfloor\le2\lceil\sqrt{n}\rceil$. Let's prove this by induction.
It holds for $n\le 2$, so suppose it holds for $n\le N-1$. We want to show that $f(N)\le \lfloor\sqrt{4N-3}\rfloor$.
We have that $f(N)\le 1+f(N-\lfloor\sqrt{N}\rfloor)$, which by the inductive hypothesis, is at most $$1+\lfloor\sqrt{4(N-\lfloor\sqrt{N}\rfloor)-3}\rfloor=1+\lfloor\sqrt{4(m^2+r-m)-3}\rfloor$$ where $N=m^2+r$, with $m=\lfloor\sqrt{N}\rfloor$ and $0\le r\le 2m$. There are three cases here: $r=0$, $r\ge m+1$ and $1\le r\le m$. If $r\ge m+1$, we have that $$1+\lfloor\sqrt{4(m^2+r-m)-3}\rfloor=1+2m$$ which is the same as $\lfloor\sqrt{4N-3}\rfloor$. Similarly, if $1\le r\le m$, we have that $1+\lfloor\sqrt{4(m^2+r-m)-3}\rfloor=2m$, which is also equal to $\lfloor\sqrt{4N-3}\rfloor$. Finally, if $r=0$, $1+\lfloor\sqrt{4(m^2+r-m)-3}\rfloor=1+\lfloor\sqrt{4(m^2-m)-3}\rfloor=2m-1$, which again, is equal to $\lfloor\sqrt{4N-3}\rfloor$.
I didn't go through the nitty-gritty details, but I'll provide an example for going through them with $r\ge m+1$. If $r\ge m+1$, we have $\lfloor\sqrt{4N-3}\rfloor=\lfloor\sqrt{4m^2+4r-3}\rfloor$. We have $4m^2+4r-3\ge 4m^2+4(m+1)-3=4m^2+4m+1=(2m+1)^2$, so $\lfloor\sqrt{4m^2+4r-3}\rfloor\ge 2m+1$. And $\lfloor\sqrt{4m^2+4r-3}\rfloor\le\sqrt{4m^2+4r-3}\le\sqrt{4m^2+4(2m)-3}<\sqrt{4m^2+8m+4}=2m+2$, so $\lfloor\sqrt{4m^2+4r-3}\rfloor\le 2m+1.
So that means $\lfloor\sqrt{4N-3}\rfloor=2m+1$. Similarly, you can set up inequalities to show that $1+\lfloor\sqrt{4(m^2+r-m)-3}\rfloor=2m+1$.