Edges in a graph with no triangles

Consider a graph $H$ that has $n$ vertices, for any 3 vertices at least one of the edges amongst them is missing, and has the maximal number of edges. Consider two vertices $a,b$ that are not adjacent in $H.$ Let $A$ be the neighbours of $a$ and $B$ be the neighbours of $b$ . There cannot be any edges between vertices of $A$ , since this would violate our condition, and similarly there are no edges between vertices of $B.$ Since $H$ has the maximal number of edges, we must have $\vert A \vert = \vert B \vert$ , since otherwise we could find a graph with a larger number of edges. We can let $b$ have neighbour set $A$ and get a new graph that still has a maximal number of edges. We can repeat this process for every vertex that is not adjacent to $a,$ and we have now divided our graph into two parts, the set $A$ which has no edges between vertices, and the set $V(H) - A$ which also has no edges between vertices. For any vertex $c \in A$ and $d \not\in A$ , the edge $cd$ is present, so the number of edges in $H$ is $\vert A \vert \times (n - \vert A \vert)$ . We know this is maximized when $\vert A \vert = \lfloor \frac{n}{2} \rfloor \mbox{ and } n - \vert A \vert = \lceil \frac{n}{2} \rceil$ (or vice versa). Thus, the maximal number of edges is $\lfloor \frac{n}{2} \rfloor \lceil \frac{n}{2} \rceil$ . We have $447 \times 447 = 199809,$ so a graph with the desired property on 894 vertices can have a maximum of 199809 edges. We also have $447 \times 448 = 200256$ , so $n = 895$ is the least number of vertices that $G$ could have.

Let the least number of vertices that G can have be n So we name the vertices V 1 , V 2 , V 3 , V 4 , V 5 , V 6, .... V n clockwise direction. Now let us see what actually is happening. We first join all the vertices in the perimeter , that is , V 1V 2 , V 2V 3 , V 3V 4 ,... , V n-1V n and then we join the diagonals keeping the rule in mind. We observe, that starting from V 1, we cannot join V 3 because then V 1V 2 , V 2V 3 and V 3V 1 will form the vertices of a triangle and which we cannot do by the condition given in the problem. So we don't join V 3 with V 1. But we can join V 4 with V 1. Again, we cannot join V 1 with V 5 because then V 1V 2 , V 2V 5 and V 1V 5 will form the sides of a triangle. But we can join V 1 with V 6. So we observe that selecting any 1 vertex , we don't join the next vertex. In this case, working clockwise, we leave one vertex, join one vertex with V 1 and again leave 1 vertex. So when selecting V 1 , out of the remaining (n-1) vertices , we join \small\frac(n-1) 2 . SO the total number of edges for n vertices = \frac{n(n-1)}2 But we are over-counting as 1 edge is shared by 2 vertices. so the total number of edges for V n vertices reduces to \frac{n(n-1)}4 (i) So we get \frac{n(n-1)}4 = 200000 this reduces to n^2 - n - 800000 = 0 solving using sridhar acharya we see that \Large n=\frac{-b\pm\sqrt{b^2-4ac}}{2a} = \Large n=\frac{1\pm\sqrt{1+320000}}{2} = \Large n=\frac{1\pm\sqrt{3200001}}{2} we neglect the -ve sign as it will lead to negative number of vertices so, \Large n=\frac{1 + \sqrt{1+320000}}{2} or, \Large n=\frac{1 + \sqrt{320001}}{2} Now, it is quite obvious that we may not find a perfect integer solution to this as there may not be a completely connected graph with exactly 200000 under the given condition. So we need to make a lttle approximation. we see that for the graph to have 200000 edges , our required number of vertices , n, should be \frac{1 + \sqrt{320001}}{2} = \frac{1 + 1788.854 }{2} = \frac{1789.854 }{2} = 894.927 So in order to get exactly 200000 edges , we should have 894.927 vertices. But as the number of vertices cannot be negative , the least number of vertices required = the least integer greater than or equal to 894.927 = 895. putting this value in our equation (i) , we see that the edges count to 200032.5 ( the decimal for our approximation) we make take it as 200032 or 200033. One may not join any 33 of the edges and get the required 200000 edges. If we take n = 894 , then the total egdes count to 199585.5 which is less than 200000. So 895 is indeed our solution.