Connected simple graph
Source: Turkey JBMO Team Selection Test Problem 8
May 30, 2012
floor functionceiling functioncombinatorics proposedcombinatorics
Problem Statement
Let be a connected simple graph. When we add an edge to (between two unconnected vertices), then using at most 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.