China National Team Selection Test

For any two distinct vertices $u$ and $v$, we say that the distance between $u$ and $v$ is the shortest length of the route between $u$ and $v$. Consider a graph $G^*$ with vertex set $\{x_1, x_2, \dots, x_{3n^2-n}, y_1, y_2, \dots, y_n\}$, where $y_i$ and $x_i$ are adjacent ($1 \le i < j \le n$), $x_i$ and $x_j$ are not adjacent ($1 \le i < j \le 3n^2 - n$), $x_i$ and $y_j$ are adjacent if and only if $i \equiv j \pmod{n}$. Thus, the degree of each $x_i$ is $1$, and the degree of $y_i$ does not exceed
$$n - 1 + \frac{3n^2 - n}{n} = 4n - 2.$$
It is easy to see that the distance between $x_i$ and $x_j$ is not greater than $3$. So graph $G^*$ satisfies the condition of the problem. $G^*$ has $N = 3n^2 - n + C_n^2 = \frac{7}{2}n^2 - \frac{3}{2}n$ edges.

In the following, we show that any graph $G = G(V, E)$ satisfying the condition of the problem has at least $N$ edges. Let $X \subseteq V$ be the set of vertices with degree $1$, $Y \subseteq (V\setminus X)$ be the set of remaining vertices adjacent to $X$, and $Z \subseteq V\setminus(X \cup Y)$ be the set of remaining vertices adjacent to $Y$. Let $W = V\setminus(X \cup Y \cup Z)$. We will point out the following facts.

Property 1. Any two vertices in $Y$ are adjacent. This is because of the fact that if $y_1, y_2 \in Y$ are two vertices, there exist $x_1, x_2 \in X$ that are adjacent to $y_1$ and $y_2$, respectively; hence $y_1$ and $y_2$ are adjacent since the distance between $x_1$ and $x_2$ is not greater than $3$.

Property 2. The distance between vertex in $W$ and vertex in $Y$ is $2$. This is because of the fact that if the distance between $w_0 \in W$ and $y_0 \in Y$ is greater than $2$ (obviously, distance $>1$), suppose that $x_0 \in X$ is adjacent to $y_0$, then the distance between $w_0$ and $x_0$ is greater than $3$, which is a contradiction. Furthermore, we know this Property 2 means each vertex in $W$ is adjacent to some vertex in $Z$.

Denote by $x, y, z$ and $w$ the numbers of elements in sets $X, Y, Z$ and $W$, respectively. Now count the number of edges; there are $C_y^2$ edges between points in $Y$, $x$ edges from points of $X$ to $Y$, at least $z$ edges from points of $Z$ to $Y$, and at least $w$ edges from points of $W$ to $Z$. So, if $y \ge n$, then
$$|E| \ge C_y^2 + x + z + w = 3n^2 + C_y^2 - y \ge 3n^2 + C_n^2 - n = N,$$
and if $y \le n-1$, since each degree of vertex is at most $4n$,
$$\begin{align*} x + z &\le y(4n - (y - 1)) = y(4n + 1 - y) \\ &\le (n - 1)(3n + 2) = 3n^2 - n - 2, \\ \omega &\ge 3n^2 - y - y(4n + 1 - y) \ge 3. \end{align*}$$
Select a vertex $P$ in $W$ such that $P$ is adjacent as less as possible to vertices in $Z$. Suppose the least number is $a$, $a > 0$ (by Property 2). Denote the set of these $a$ vertices by $N_P \subseteq Z$.

Counting the number of the edges again, there are $C_y^2$ edges between points in $Y$, $x$ edges from points of $X$ to $Y$, at least $y$ edges from points of $N_P$ to $Y$ (by Property 2, the distance from $P$ to vertex in $Y$ is $2$), at least $z - a$ edges from points of $Z \setminus N_P$ to $Y$, and at least $aw$ edges from points of $W$ to $Z$. Thus,
$$\begin{align*} |E| &\ge C_y^2 + x + y + z - a + aw \\ &= 3n^2 - 1 + C_y^2 + (a - 1)(w - 1). \end{align*}$$
If $a > 1$, then
$$\begin{align*} |E| &\ge 3n^2 - 1 + C_y^2 + (w - 1) \\ &\ge 3n^2 - 2 + C_y^2 + 3n^2 - y - y(4n + 1 - y) > N. \end{align*}$$
If $a = 1$, since the degree of each vertex in $W$ is at least $2$, when we count the edges from points of $W$ to $Z$, we should add at least $w/2$ edges, so
$$\begin{align*} |E| &\ge 3n^2 - 1 + C_y^2 + \frac{1}{2}\omega \\ &\ge 3n^2 - 1 + C_y^2 + \frac{1}{2}(3n^2 - y - y(4n + 1 - y)) > N. \end{align*}$$
Summing up, the least number of edges is $N = \frac{7}{2}n^2 - \frac{3}{2}n$.