Prove that you need to add $1/3$ of the edges in a graph with $n > 3$ vertices to make it complete by the binomial coefficient?

68 Views Asked by At

Suppose we have a complete graph with $ > 3$ vertices and theoretically want to make it triangle free, to do this we should remove at least $1/3$ of the initial amount of edges? Now I am thinking about the reverse of this question – how can I mathematically prove/show that we would need to add $1/3$ of the removed edges back to make it complete again? In my previous question, I mentioned that I wanted to solve the problem using the binomial coefficient with $B(n,2)= n(n-1)/2$ where $1$ edge $= (n-2)$ triangles.