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?

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

269

wrong

To find the least number of vertices that the graph G can have, let's analyze the given condition. It states that for any three vertices v, w, x, at least one of the edges vw, wx, xv is not present.

Let's assume that G has n vertices. In the worst-case scenario, each edge is present between any two vertices of the set {v, w, x}. So, for any three vertices, there are three possible edges between them. Since at least one edge is missing, there can be at most two edges present between any three vertices.

Now, we need to find the maximum possible number of edges in the graph G with n vertices. In a simple graph, each pair of vertices can have at most one edge between them. So, the maximum number of edges in a simple graph with n vertices can be given by the formula:

Maximum number of edges = n * (n - 1) / 2

According to the condition, the maximum number of edges in G cannot exceed 200,000. Therefore, we have the equation:

n * (n - 1) / 2 ≤ 200,000

To find the least number of vertices that G can have, we need to solve this equation. Let's solve it step by step:

1. Multiply both sides of the equation by 2 to eliminate the fraction:

n * (n - 1) ≤ 400,000

2. Expand the left side of the equation:

n^2 - n ≤ 400,000

3. Move all terms to one side of the equation:

n^2 - n - 400,000 ≤ 0

4. Now, we have a quadratic inequality. To solve it, we can factorize the quadratic or use the quadratic formula. In this case, let's factorize:

(n - 400)(n + 1000) ≤ 0

5. Set each factor less than or equal to zero:

n - 400 ≤ 0 OR n + 1000 ≤ 0
n ≤ 400 n ≤ -1000

6. Disregard the negative solution since the number of vertices cannot be negative:

n ≤ 400

Therefore, the least number of vertices that the graph G can have is 400.