A 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?

16

wrong...blunder..even for a simple graph with all vertices connected is given by n(n=1)/2 for 16 it is 15*8<<200000

538

895

To determine the least number of vertices in graph G, we need to understand the conditions given.

The problem states that for any 3 vertices v, w, x in G, at least one of the edges vw, wx, xv is not present. In other words, at least one of the three possible edges between any three vertices is missing.

Let's consider the worst-case scenario to find the least number of vertices. The smallest possible number of vertices that can satisfy this condition is when the graph is a complete graph. In a complete graph, there is an edge between every pair of vertices.

In a complete graph, the number of edges can be determined using the formula:

E = (n * (n - 1)) / 2

Where E is the number of edges and n is the number of vertices.

Given that G has 200,000 edges, we can rearrange the formula to solve for n:

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

Multiplying both sides by 2:

400,000 = n * (n - 1)

Simplifying further:

n^2 - n - 400,000 = 0

Now we can solve this quadratic equation to find the value of n. Using the quadratic formula:

n = (-b ± √(b^2 - 4ac)) / 2a

For this equation, a = 1, b = -1, and c = -400,000. Substituting these values into the formula:

n = (1 ± √(1 - 4(-400,000))) / 2

n = (1 ± √(1 + 1,600,000)) / 2

n = (1 ± √1,601,000) / 2

n ≈ (1 ± 4001) / 2

We take the positive value since the number of vertices cannot be negative:

n ≈ (1 + 4001) / 2

n ≈ 2001/2

n ≈ 1000.5

Since the number of vertices must be a whole number, the least number of vertices that G can have is 1001.

Therefore, the least number of vertices in graph G is 1001.