Question

If G is a connected undirected graph such that every vertex has degree at most k, and the shortest path between any two vertices has length at most 2, then the number of vertices in G can be at most?​

Answer 1

Answer: 37

The highest degree can be 6, as stated, by connecting 6 vertices to a central vertex and 5 vertices to each of them, however, this violates the shortest path criteria. As a result of the further explanation and dot connection, the correct answer is 37.

#SPJ3