MathDB
Miklos Schweitzer 1982_3

Source:

January 31, 2009
combinatorics proposedcombinatorics

Problem Statement

Let G(V,E) G(V,E) be a connected graph, and let dG(x,y) d_G(x,y) denote the length of the shortest path joining x x and y y in G G. Let r_G(x)\equal{} \max \{ d_G(x,y) : \; y \in V \ \} for x∈V x \in V, and let r(G)\equal{} \min \{ r_G(x) : \;x \in V\ \}. Show that if r(G)≥2 r(G) \geq 2, then G G contains a path of length 2r(G)\minus{}2 as an induced subgraph. V. T. Sos
Back to ProblemsView on AoPS