Edges in a graph with no triangles

A simple graph G G has 200000 edges and for any 3 vertices v , w , x , v,w,x, at least one of the edges v w , w x , x v vw, wx, xv is not present in G . G. What is the least number of vertices that G G can have?

Details and assumptions

A simple graph does not have multiple edges between vertices, or self loops.


The answer is 895.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Calvin Lin Staff
May 13, 2014

Consider a graph H H that has n 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 a,b that are not adjacent in H . H. Let A A be the neighbours of a a and B B be the neighbours of b b . There cannot be any edges between vertices of A A , since this would violate our condition, and similarly there are no edges between vertices of B . B. Since H H has the maximal number of edges, we must have A = B \vert A \vert = \vert B \vert , since otherwise we could find a graph with a larger number of edges. We can let b b have neighbour set A 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 , a, and we have now divided our graph into two parts, the set A A which has no edges between vertices, and the set V ( H ) A V(H) - A which also has no edges between vertices. For any vertex c A c \in A and d ∉ A d \not\in A , the edge c d cd is present, so the number of edges in H H is A × ( n A ) \vert A \vert \times (n - \vert A \vert) . We know this is maximized when A = n 2 and n A = n 2 \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 n 2 n 2 \lfloor \frac{n}{2} \rfloor \lceil \frac{n}{2} \rceil . We have 447 × 447 = 199809 , 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 × 448 = 200256 447 \times 448 = 200256 , so n = 895 n = 895 is the least number of vertices that G G could have.

Sagnik Saha
May 20, 2014

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.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...