What is the smallest number of edges in a graph with $20$ vertices for which it is true that any subgraph on $5$ vertices of this graph is connected.

Question

Let’s look at country with $20$ towns in there with roads between them. It is right that for any subset $A$ of $5$ towns of this country, for any town from A you can reach any town of $A$ using only roads between towns in A. i.e., any subgraph of $5$ vertices is connected. What is the minimum number of roads possible?

Answer 1

Our first observation is that, as discussed in the comments, the minimum degree has to be $16$. To see that this holds, assume for contradiction that there exists $v$ with degree $|N(v)|<16$, where $N(v)$ is the neighborhood of $v$. But then we have $|N(v)\cup\{v\}|\le 16$ and hence there are at least $|V|\ge 4$ remaining vertices, where $V=(N(v)\cup\{v\})^{\mathrm c}$ is the complement of $N(v)\cup\{v\}$. Choose the induced subgraph on $\{v\}\cup U$, where $U\subseteq V$ has size $|U|=4$, then $v$ is isolated in the subgraph since none of the vertices in $U\subseteq V$ are adjacent to $v$. Thus, we found a subgraph on five vertices that is not connected, a contradiction.

By the handshaking lemma we know that the number of edges is $\frac 12\sum_v|N(v)|\ge \frac 12\cdot20\cdot 16=160$ with equality if and only if the graph is $16$-regular. But the following $16$-regular graph has the desired property: the eight power of the cycle on 20 vertices. In this graph, $v_0$ is adjacent to $v_1,\dots,v_8$ and to $v_{12},\dots,v_{19}$. It is not adjacent to $v_9,\dots,v_{11}$. Analogously to $v_0$, each vertex is adjacent to the next eight vertices and the previous eight vertices. For example, $v_1$ is adjacent to $v_2,\dots,v_9$ and to $v_{13},\dots,v_{19},v_0$. This is the 16-regular graph that we consider. Now, let us choose any five vertices and check if the induced subgraph is connected. These are many choices, and we will only discuss the relevant ones (the other ones will then be immediately clear).

Say, we first choose $v_0$. Now, we have to choose another four vertices. But there are only three vertices which are not adjacent to $v_0$ (namely $v_9,v_{10},v_{11}$), so we have to choose one vertex which is adjacent to $v_0$. Let's assume first that this adjacent vertex is $v_1$. Then we still have to choose three vertices, but only two vertices are not adjacent to $v_0$ and not adjacent to $v_1$ (namely $v_{10}$ and $v_{11}$), so we have to choose one which is adjacent to $v_0$ or to $v_1$. Let's assume first that this adjacent vertex is $v_2$. We still have to add two vertices, but only the vertex $v_{11}$ is not adjacent to any of $v_0,v_1,v_2$, so one of the two remaining vertices has to be adjacent to $v_0,v_1$ or $v_2$. To be precise, we have to pick a vertex $u\in\{v_3,\dots,v_{19}\}\setminus\{v_{11}\}$. But no matter what $u$ we pick, it will definitely be adjacent to $v_{11}$. Now, we have to pick one remaining vertex $w\in\{v_3,\dots,v_{19}\}\setminus\{u\}$. But no matter which $w$ we pick, it will now be definitely adjacent to $v_0,v_1,v_2$ or $w$. This means that from $v_0$ we can reach $v_1,v_2$ (which are adjacent), from these three we can reach $u$ (by definition of $u$) and from these four we can reach $w$ (by definition of $w$). So for the case that we first picked $v_0,v_1,v_2$ the induced subgraph will be connected.

If we pick $v_0,v_1$ and then $v_{19}$ instead of $v_2$, the situation is symmetric and hence the induced subgraph is again connected.

So, let's assume that we pick $v_0$, $v_1$ and then some $w\in\{v_3,\dots,v_{18}\}$. Then all of the remaining vertices $\{v_2,\dots,v_{19}\}\setminus\{w\}$ are necessarily adjacent to $v_0,v_1$ or $w$ (because $w\not\in\{v_{19},v_0,v_1,v_2\}$ has to be adjacent to both $v_{10}$ and $v_{11}$). So, not matter which two remaining vertices we pick from $\{v_2,\dots,v_{19}\}\setminus\{w\}$, they will be adjacent to $v_0,v_1$ or $w$. But then the induced subgraph has to be connected (as before). This shows that if we pick $v_0$ first, then $v_1$ and no matter what other three vertices, the induced subgraph will definitely be connected.

Notice that if we pick $v_{19}$ instead of $v_1$, the situation is symmetric and hence also in this case the induced subgraph will be connected. So, assume that we first pick $v_0$ and then $v_2$. Then the only vertex which is not adjacent to $v_0$ and not adjacent to $v_2$ is $v_{11}$. But since we still have to choose three vertices, we have to pick some $w\in\{v_1,v_3,\dots,v_{19}\}\setminus\{v_{11}\}$ which is adjacent to $v_0$ or $v_2$. If we pick $w=v_1$, we end up in a case that we already discussed, and for any other choice $w$ will necessarily be adjacent to $v_{11}$. But now, no matter what we choose for the remaining two vertices, they have to be adjacent to $v_0,v_1$ or $w$. As before, this shows that the induced subgraph is connected. This settles all cases where we start with $v_0$ and $v_2$. The cases where we start with $v_0$ and $v_{18}$ follow by symmetry.

So, what's left are the cases where we first pick $v_0$ and then some $w\in\{v_3,\dots,v_{19}\}\setminus\{v_9,\dots,v_{11}\}$ (since we said above that the second vertex has to be adjacent to $v_0$). But for any such choice all of the three remaining vertices have to be adjacent to $v_0$ or $w$, so as before the induced subgraph will have to be connected.

Now, the last remaining question is what happens if we start with some other vertex than $v_0$. But then, we notice that the situation is again symmetric, so the induced subgraph will be connected. This completes the discussion of the last case.

Final Remark: Consider twenty points distributed evenly on a circle such that any two neighbors are distance one apart. Formally, take the circle of radius $r=10/\pi$ centered at the origin and $v_i=(r\cos(\pi/10i),r\sin(\pi/10i))$ for $0\le i<20$. Any choice of five of these points induces a partition of the circumference in five parts with integer lengths $x_1,\dots,x_5$. Above, we mainly showed that there cannot be two parts with length more than eight, since otherwise $x_1+\cdots+x_5\ge 2\cdot 9+3\cdot 1=21>20$, i.e. the total length is exceeded. The remainder was mostly the graph theoretical interpretation of this result.

Answer 2

For a simpler construction of a $16$-regular graph with this property, take the Turán graph $T(20,5)$. That is, we have vertices $v_{i,j}$ with $1 \le i \le 4$ and $1 \le j \le 5$, and we connect two vertices $v_{i,j}$ and $v_{i',j'}$ when $j \ne j'$. In other words, we can partition the vertices into five sets $V_1, V_2, V_3, V_4, V_5$, where each $V_j$ is $\{v_{1,j}, v_{2,j}, v_{3,j}, v_{4,j}\}$, so that each vertex is adjacent to all others except the three in its own set.

If we select any $5$ vertices from this graph, they cannot all be from the same set $V_j$, because $|V_j|=4$ for each $j$. Suppose we select $k>0$ vertices from some set $V_j$, and $5-k$ vertices from outside $V_j$. Then, in particular, the edges in the induced subgraph include all edges between the $k$ vertices in $V_j$ and the $5-k$ vertices not in $V_j$, so our subgraph contains all the edges of the complete bipartite graph $K_{k,5-k}$. All four options here - $K_{1,4}$, $K_{2,3}$, $K_{3,2}$, and $K_{4,1}$ - are connected, so the subgraph is connected.