MathDB
Maximal diameter of graph with minimum degree 42

Source: Bundeswettbewerb Mathematik 2023, Round 2 - Problem 2

September 8, 2023
combinatorics proposedcombinatoricsgraph theory

Problem Statement

A hilly island has 20232023 lookouts. It is known that each of them is in line of sight with at least 4242 of the other lookouts. For any two distinct lookouts XX and YY there is a positive integer nn and lookouts A1,A2,,An+1A_1,A_2,\dots,A_{n+1} such that A1=XA_1=X and An+1=YA_{n+1}=Y and A1A_1 is in line of sight with A2A_2, A2A_2 with A3A_3, \dots and AnA_n with An+1A_{n+1}. The smallest such number nn is called the viewing distance of XX and YY.
Determine the largest possible viewing distance that can exist between two lookouts under these conditions.