Diameter of a graph given the Independence number

104 Views Asked by At

How to prove that the diameter of an undirected simple graph is at most 3 if its independence number equals 2

1

There are 1 best solutions below

0
On BEST ANSWER

Assume the diameter is larger than 3, say 4. then we get a path on 5 vertices, which is a shortest path connecting its endpoints. Hence the endpoints and the vertex in the middle are not adjacent whatsoever. We have found an independent set of size three. A contradiction.