Suppose that the radius of a graph G is r How far in terms o

Suppose that the radius of a graph G is r. How far (in terms of r) from the center of G can be a vertex of eccentricity r + 1? (Hint: Far. For the construction, use a connected graph with exactly one cycle in it.)

Solution

For a non-connected graph the eccentricity of the vertices are infinity. So, let us stick to connected graphs.

For a connected graph G, let H be the subgraph which is the center of G. Then each vertex of H has the eccentricity r.

Since H is the center, any shortest path between any two vertices passes through one of the vertices of H. That is, when you calculate the eccentricity, the shortest path followed will be through H. And all the vertices in H has an eccentricity r. Therefore, the vertices with the ecentricity r+1 will be adjacent to one of the vertices in H.