A simple graph G has 200000 edges and for any 3 vertices v,w,x, at least one of the edges vw,wx,xv is not present in G. What is the least number of vertices that G can have?
147
To determine the least number of vertices that the graph G can have, we need to understand the relationship between the number of edges and the vertices in the graph.
According to the given condition, for any three vertices v, w, and x, at least one of the edges vw, wx, or xv is not present in G. Let's consider a scenario where all three edges are present between every three vertices in G.
If all three edges are present, it means that for every pair of vertices, there are at least two edges connecting them. For simplicity, let's denote the number of vertices as n.
Each vertex can be connected to (n-1) other vertices, giving (n-1) possible edges for each vertex. Therefore, the total number of edges in G can be calculated as: (n-1) * n / 2, which is equivalent to the formula for the number of edges in a complete graph.
Given that G has 200,000 edges, we can solve the equation to find the appropriate value of n:
(n-1) * n / 2 = 200,000
Expanding and rearranging the equation, we have:
n^2 - n - 400,000 = 0
By solving this quadratic equation, we determine that n ≈ 632.4555. Since the number of vertices should be a whole number, we round up to the nearest integer.
Therefore, the least number of vertices that G can have is 633.