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^{\ast }$ 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(\mathrm{mod}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^{\ast }$ satisfies the condition of the problem. $G^{\ast }$ 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{array}{rl}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{array}$$ 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{array}{rl}|E|& \ge C_y^2+x+y+z-a+aw\\ & =3n^2-1+C_y^2+(a-1)(w-1).\end{array}$$ If $a>1$, then $$\begin{array}{rl}|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{array}$$ 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{array}{rl}|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{array}$$ Summing up, the least number of edges is $N=\frac{7}{2}{n}^2-\frac{3}{2}n$.