How to prove that the diameter of an undirected simple graph is at most 3 if its independence number equals 2
2026-05-17 14:35:12.1779028512
Diameter of a graph given the Independence number
104 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
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.