Graph Theory / combinatorics question

Question

Here a problem from Graph Theory I can not solve. There are $2023$ viewpoints on an island. We know that each viewpoint has line of sight to at least $42$ other viewpoints. You should note that, if a viewpoint $A$ has a line of sight with the viewpoint $B$, then also $B$ with $A$.
Furthermore, for two different viewpoints $a$ and $b$, there is a positive integer $n$ and viewpoints $A_1, A_2,\dots , A_{n+1}$ so that $A_1=a$ and $A_{n+1} = b$ and $A_1$ with $A_2$, $A_2$ with $A_3$ and $\dots A_n$ with $A_{n+1}$ has line of sight. We call the smallest such number $n$ the viewing distance between $a$ and $b$.

The question is to determine the greatest viewing distance that two different viewpoints can have under these conditions.
My approach: it seems as if I could be able to solve it with the pigeonhole principle, because I already solved a similar problem, but I do not know how, and it is a problem from Graph Theory.

Answer 1

Let us encode this as a graph theory problem. We seek a graph of maximum diameter (longest shortest path) that is connected, has 2023 vertices, has minimum degree 42.

A trivial upper bound for the diameter of a graph is the number of vertices minus 1, i.e. 2022 in our case. The only graph on 2023 vertices with diameter 2022 is a path. Increasing the minimum degree decreases the diameter, as we can in some sense "shortcut" using additional edges.

Let us tackle the same problem with some smaller numbers to get an idea of what is going on. Let us consider a graph with $7$ vertices and vertices, where all have degree at least $3$. Then every pair of non-neighbours have a neighbour in common, so the diameter is at most $2$. Since there can be non-neighbours, it is exactly 2. A similar type of analysis on distance $k$ neighbourhoods can be made for graphs with more vertices.

Another way to see this is as follows. Let us order the vertices $v_1, \dots, v_7$. Let us try to maximize the shortest path between $v_1$ and $v_7$. Without loss of generality, $v_1$ is adjacent to $v_2, v_3, v_4$. Greedily continuing like this, $v_2$ is also adjacent to $v_3, v_4$, $v_3$ is adjacent to $v_4$. Now, $v_1, v_2, v_3, v_4$ all have degree at least $3$. Repeat the same process from the other direction starting at $v_7$. We obtain two $K_4$ graphs glued at a vertex. The same type of construction, gluing copies of $K_4$ in this pathlike way, would work for any number of vertices $n$. Let us denote such a graph $G(n,3)$. Then, the diameter $d$ of $G(n,3)$ is $d = \lceil\frac{n}{4}\rceil$.

Now the analoguous construction for your numbers, $G(2023,42)$, has diameter $d=\lceil\frac{2023}{42}\rceil = 49$. Thus, the number you are looking for is at least 49; I believe it is exactly 49, perhaps you can prove this?

Answer 2

I can get a diameter of $139$. The inspiration comes from the below figure for $9$ viewpoints where each can see $2$. The greatest diameter for a connected graph is $9$ for a path but the two endpoints only can see one other viewpoint. Instead of connecting them to make a cycle and cutting the diameter in half, we curl each one around and get a diameter of $7$.

We make a similar figure with each dot representing $14$ or $15$ viewpoints. Dots $C$, $G$, and every third dot in between represent $15$ viewpoints. All the viewpoints in a dot can see all the viewpoints in its dot and all the ones in the dots it is connected to. That gives the required $42$ visible viewpoints. We get $141$ dots and have two viewpoints left over that can be placed in any dots. The diameter is $139$

Answer 3

Suppose a connected graph contains 2023 vertices, with a diameter of at least 141 and a minimum degree of 42. Let $v_0$ represent one endpoint of its longest path. Denote by $x_i$ the count of vertices that are at a distance of $i$ from $v_0$. For $0\leq i \leq 141$, it follows that $$x_{i-1}+x_{i}+x_{i+1}\geq43,$$ where $x_{-1}=0$ for convenience. Summing these 142 inequalities results in $$3(x_0+x_1+\dots+x_{141})\geq 6106.$$ However, with a total of 2023 vertices, it is known that $$x_0+x_1+\dots+x_{141}\leq2023,$$ leading to a contradiction.

We assemble a sequence by linking complete graphs: starting with $K_1$, $K_{42}$, and $K_1$, then continuing with a pattern of $K_1$, $K_{41}$, $K_1$, $K_1$, $K_{41}$, $K_1$, and so on，finally concludes with $K_1$, $K_{42}$, $K_1$. This creates a graph comprising 2023 vertices, featuring a diameter of 140 and a minimum degree of 42.

In conclusion, the answer is 140.