Problem

Source: Turkey JBMO Team Selection Test Problem 8

Tags: floor function, ceiling function, combinatorics proposed, combinatorics



Let $G$ be a connected simple graph. When we add an edge to $G$ (between two unconnected vertices), then using at most $17$ edges we can reach any vertex from any other vertex. Find the maximum number of edges to be used to reach any vertex from any other vertex in the original graph, i.e. in the graph before we add an edge.