The conclusion does not seem correct. Consider a tree of depth $2$ rooted at $a.$ Let $a$ have $3n/4$ children. Each child of $a$ has $4n-1$ children, except for two which have $4n-2$. Attach a single vertex $b$ to $a$. As a result we have a tree with $3n^2$ vertices. Now connect every pair of children of $a$ with an edge. As a result, we have a graph that has about $(3n/4)^2/2 = 9n^2/32$ edges more than the spanning tree. This graph has diameter $3$. However, the conclusion of the problem requires that the graph to have $n^2/2$ edges more than the spanning tree, which is more than necessary.

ninjaturtle wrote: Now connect every pair of children of $a$ with an edge. This condition breaks the problem condition that "the degree of each vertex of $G$ is not greater than $4n$".

Solution : http://www.math.uiuc.edu/~z-furedi/PUBS/furedi_minimal-diameter-3-graphs.pdf

Algorithm for finding minimal configuration: What does $\frac{7n^2-3n}{2}$ mean? some simple calulations show it is equal to $ (4n-2)n- \frac{n(n-1)}{2}$ so a minimal configuration is given by a $K_n$ with each vertex having degree 4n-2( i will atach a picture for better understanding) Hint for the rest of the proof: asume x is the minimal number of edges neaded and show that the form of the graph is like the one of the proof, a complete $K_X$ with vertexes atached to the vertexes of the polygon and prove that $x>n-1$ using the contradiction by the 4n degree bound.

Attachments:

Anyone for more details?Good problem.

Any ideas?

The post #4 has a link to a paper which contains a more general version, with a complete proof. I am posting below the subset of that paper needed to solve the China TST problem, with significant re-wording for clarity. For the equality case, take a porcupine graph defined as follows: we take a clique $K_n$ and attach $3n-1$ leaves on each of the $n$ vertices. This porcupine has max degree $4n-2$, and indeed exactly \[ n(3n-1) + \binom n2 = \frac{7n^2-3n}{2} \]edges. (Intuitively, the porcupine is not too far from a tree, and so we expect to consider mostly graphs with low average degree, close to $2$.) The hard part is showing the bound. We divide vertices into five categories. A village is a vertex of degree $1$. The city consists of all vertices adjacent to a village. The desert consists of vertices not adjacent to a city. The plains consists of vertices adjacent to the desert. Finally, the lake consists of the remaining vertices (adjacent to the city, not a leaf, and not adjacent to desert). It is probably helpful to draw a picture of these. Claim: The cities form a clique $K_x$, where $x$ denotes the number of cities. Proof. Otherwise the corresponding villages would not be reachable in $3$ steps. $\blacksquare$ In this way, we already have length $3$ paths between any two non-desert vertices (using layovers in the city). So the tricky part is dealing with the ill-connected desert. We are going to consider three different cases. Case 1: the desert is empty. Then we can delete any edges not touching a city and maintain the diameter at most $3$. A calculation gives the number of edges to now be $\binom{x-1}{2} + (3n^2-1)$. On the other hand, by considering the average degree of a city, we must have \[ 4n \ge (x-1) + \frac{3n^2-x}{x} \]which forces $x \ge 2n+1 - \sqrt{n^2+4n+1} > n-1$. So $x \ge n$ and this gives the bound. Case 2: the desert is nonempty. Let $D$ denote the desert, and let $H$ denote the subgraph of $G$ obtained by deleting $D$. We consider two subcases: Case 2a: some desert vertex $v$ is adjacent to exactly one plain vertex $w$. Then $w$ must be connected to every vertex of the city, in order for there to be a path from $v$ to each village. Consequently, in the graph $H$, we get a clique on $x+1$ vertices consisting of the city plus $H$. Thus we can delete at least $\binom{(x+1)-1}{2} = \binom x2$ vertices from this clique while keeping $H$ connected. Thus \[ \#E(H) \ge \#V(H) - 1 + \binom x2. \](Here we have used the information of $w$ to get $\binom x2$ as opposed to the more natural $\binom{x-1}{2}$.) As for the desert, each desert vertex has at least one edge to the plains, and moreover all desert vertices have degree at least $2$. So we see that there were at least $\frac32 \#V(D)$ edges touching the desert. Summing these two gives that \[ \#E(G) \ge \frac{1}{2} \#V(D) + \#V(G) - 1 + \binom x2. \] Case 2b: every desert vertex is adjacent to $t \ge 2$ or more vertices in the plains. Assume $t$ is minimal, let $w_1$, \dots, $w_t$ be said neighbors. Each city must be adjacent to some $w_i$, and so by a similar argument as before, we can $\binom{x-1}{2} + (x-t)$ edges from $H$ while keeping it connected. Thus $\#E(H) \ge \#V(H) - 1 + \binom{x-1}{2} + x - t = \#V(H) + \binom x2 - t$. This time, there are at least $t\#V(D)$ edges touching the desert (and we can disregard desert-internal edges this time; there need not be any). So \begin{align*} \#E(G) &\ge t\#V(D) + \#V(H) + \binom{x}{2} - t \\ &= \#V(G) + (t-1)(\#V(D)-1) - 1 + \binom{x}{2} \\ &\ge \#V(G) + \binom x2 - 2 + \#V(D). \end{align*}since $t \ge 2$. By taking the minimum of the two sub-cases, we find \[ \#E(G) \ge \# V(G) + \binom x2 - 1 + \left\lfloor \#V(D)/2 \right\rfloor. \]Now we will let $y = \#V(H) - x$ denote the number of vertices among villages, plains, and lake; let $z = \#V(D) > 0$ denote the number of vertices in the desert. Thus $\#V(G) = x+y+z$. Assume for contradiction now that $\#E(G) < \frac{7n^2-3n}{2}$. Then \begin{align*} \frac{7n^2-3n}{2} &> 3n^2 + \binom x2 - 1 + \left\lfloor \#V(D)/2 \right\rfloor \\ \iff \frac{n^2-3n+2}{2} &> \binom x2 + \left\lfloor \#V(D)/2 \right\rfloor \end{align*}which in particular forces $x < n-1$, hence $x \le n-2$. One more equation: by considering edges adjacent to at least one city (which includes an edge from every vertex counted in $y$), we also have the inequality \[ 4n \cdot x \ge 2\binom x2 + y = x^2-x+y. \]Thus the previous two equations give bounds on $y$ and $Z$ in $x$. Putting these all together now, we get \begin{align*} 3n^2 &= x+y+z \\ &\le x + \left[ 4n \cdot x - x^2 + x \right] + \left[ 2\left( \frac{n^2-3n+2}{2} - \binom x2 \right) + 1 \right] \\ &= -2x^2 + (4n+3)x + (n^2-3n+3). \end{align*}This is a parabola in $x$ whose optimum is achieved over ${\mathbb R}$ at $x = n + \frac 34$, so since $x \le n-2$, it is bounded above by its value at $x = n-2$. This evaluates to $3n^2-11 < 3n^2$, contradiction. Thus in all cases we have the desired bound on $\#E(G)$.

Here's a more motivated and less elegant approach. At each step, you take the low-hanging fruit that remains, and hope that you can pass over the bar that is $\frac{7n^2-3n}{2}$. Note. One equality case is given by the following construction. Let $A_1, A_2, \cdots, A_n$ be $n$ vertices that are pairwise adjacent; i.e. they form a complete graph on $n$ vertices. Now define vertices $B_i^j$ for $1 \le i \le n$ and $1 \le j \le 3n-1$ such that there is an edge between $B_i^j$ and $A_i$. This consists of $3n^2$ vertices in total. We can check that this works. There are exactly $\binom{n}{2}+n(3n-1) = \frac{7n^2-3n}{2}$ edges. $\blacksquare$ Let $V$ be the vertex set of $G$. Let $X$ be a vertex of degree exactly $1$. Suppose it is adjacent to vertex $Y$. We know that there is a path of length at most $3$ between $X$ and any other vertex of $G$. Let us define sets $S_1, S_2, S_3$ of vertices such that $S_i$ consists of all vertices of distance exactly $i$ from $X$. Note that $\{X \} \cup S_1 \cup S_2 \cup S_3 = V$. Furthermore, $S_1, S_2, S_3$ are disjoint, and $S_1 = \{Y\}$. All edges of $G$ are of the form $XY, YS_2, S_2S_2, S_2S_3, S_3S_3$. (We say that an edge is of form $AB$ if the edge has one endpoint in $A$ and the other endpoint in $B$.) Note that $Y$ has degree at most $4n$, so there are at most $4n-1$ vertices in $S_2$. It follows that there are at least $3n^2-4n-1$ vertices in $S_3$. Between any two vertices in $S_3$, there must be a path of length at most $3$. Each vertex $v$ in $S_3$ must be adjacent to some vertex in $S_2$. For each $v$, let us arbitrarily choose a vertex $f(v)$ in $S_2$ that is adjacent to $v$. We let $h(v)$ be the set (possibly empty) of vertices in $S_2 \setminus \{f(v)\}$ that are adjacent to $v$. The edges of form $vh(v)$ will be considered ``extra.'' For each vertex $w$ in $S_2$, we define $g(w)$ as the set of vertices $v$ in $S_3$ satisfying $f(v) = w$. Note that it is possible for $w$ to be adjacent to some vertex in $S_3$ that is not in $g(w)$. For each vertex $v$ in $S_3$, we say that it is plentiful if there exists an edge of form $vS_3$ or if $h(v)$ is nonempty. We say that a vertex $w$ in $S_2$ is deficient if there exists some vertex $v$ in $g(w)$ that is not plentiful. We say that a vertex $w$ in $S_2$ is abundant if $w$ is not deficient. Suppose there are $a$ deficient vertices. We will find a lower bound on the number of edges of $G$. Consider any two deficient vertices $w_1, w_2$. We know that there exist vertices $v_1, v_2$ respectively in $g(w_1), g(w_2)$ that are not plentiful. This means that the only vertex adjacent to $v_1$ is $w_1$, and the only vertex adjacent to $v_2$ is $w_2$. We know that there must exist a path of length at most $3$ between $v_1$ and $v_2$. It follows that $w_1, w_2$ are adjacent. Thus any two deficient vertices are adjacent. In particular, the $a$ deficient vertices must form a complete graph. Let the edges of this complete graph be of type I. If $a \ge n-1$, there are at least $\binom{n-1}{2}$ edges of form $S_2S_2$. Deleting all edges of form $S_2S_2$ will result in a subgraph that is still connected; hence, at least $3n^2-1$ edges remain after deletion. This means that originally, there must be at least $\binom{n-1}{2}+(3n^2-1) = \frac{7n^2-3n}{2}$ edges. Thus, in this case, we are done. (Our initial construction for the equality case satisfies $a = n-1$.) Now suppose $a \le n-2$. Each deficient vertex $w$ is adjacent to $Y$, to all other deficient vertices, and to some number of vertices in $S_3$. We know that the degree of $w$ is at most $4n$. Thus, $w$ is adjacent to at most $4n-a$ vertices in $S_3$. There are $a$ deficient vertices, so there are at most $a(4n-a)$ vertices in $S_3$ that are adjacent to some deficient vertex. We know that $a(4n-a) \le (n-2)(3n+2) = 3n^2-4n-4$. Since $3n^2-4n-4 < 3n^2-4n-1$, there must be at least one vertex $v_0$ in $S_3$ that is not adjacent to any deficient vertex. (In fact, there are at least 3 such vertices.) Let $F$ be the set of vertices in $S_3$ that are not adjacent to any deficient vertex. Note that $F$ contains at least $3n^2-4n-1-a(4n-a)$ vertices. Let the deficient vertices be $d_i$ for $1 \le i \le a$. Let $D$ be the set of deficient vertices. Define $e_i$ as a vertex in $g(d_i)$ that is not plentiful. There must be a path of length at most $3$ between $e_i$ and $v_0$. Such path must begin with the vertices $e_i, d_i$. Thus there must be an edge of form $d_iS_3$ (that can form path $d_iS_3v_0$) or of form $d_iS_2'$, where $S_2' = S_2 \setminus D$. Summing over $i$, we see that there are at least $a$ of these edges total. Let these edges be of type II. Note that the deletion of all type II edges can result in vertices $v$ in $S_3 \setminus F$ that are adjacent only to $v_0$. For this reason, we will ensure that no type III edges will be of the form $v_0v$, where $v$ is defined as above. Note that $F \setminus \{v_0\}$ contains at least $3n^2 - 4n - 2 - a(4n-a)$ vertices. By definition, each vertex in this set is plentiful. It follows that there are at least $\frac{1}{2}(3n^2 - 4n - 2 - a(4n-a))$ edges with at least one endpoint in $F \setminus \{v_0\}$ of form $S_3S_3$ or $vh(v)$. Let these edges be of type III. Note that no type III edges are of the form $v_0(S_3 \setminus F)$. Note that the deletion of all edges that are of type I or type II or type III results in a subgraph that is still connected; hence, at least $3n^2-1$ edges remain after this deletion. In total, we have \[\binom{a}{2}+a+\frac{1}{2}(3n^2 - 4n - 2 - a(4n-a))+(3n^2-1) = \frac{1}{2}(9n^2-4n-4+2a^2-(4n-1)a).\]This quantity is minimized when $a=n-2$, in which case we have \[\frac{1}{2}(9n^2-4n-4+(-2n^2+n+6)) = \frac{7n^2-3n+2}{2} > \frac{7n^2-3n}{2},\]as desired. $\blacksquare$

Construction: Take a $K_n$ and let each vertex of it be adjacent to $3n-1$ vertices. This makes for $n(3n-1)+n=3n^2$ vertices. Note that the maximum degree of a vertex in the resulting graph is $(n-1)+(3n-1)=4n-2$. It's easy to see that the other conditions are also satisfied. Note that number of edges in this graph $=\binom n2+ n(3n-1)= \frac {7n^2-3n}{2}$. Proof of Bound : Denote by $d(u,v)$ the minimum path length between vertices vertices $u,v$. Let $N= \tfrac {7n^2-3n}2$. We begin with some notation : Let $A$ denote the set of vertices with degree $1$. Let $B$ denote the neighborhood of $A$ Let $C$ denote the vertices which are neighbors of $B$ but not in $A$. Let $X$ denote the neighbors of $C$ that are not in $B$. We begin with two easy claims : Claim : For all $b_1,b_2 \in B$, $b_1b_2$ is an edge. Proof : Let $a_i$ be vertices in $A$ adjacent to $b_i$. To have $d(a_1,a_2)\le 3$, the claim must hold. $\square$ Claim : For all $b\in B$ and $x \in X$, we have $d(b,x)=2$ Proof : Assume if possible $d(b,x)=3$. Look at a $a\in A$ such that $ab$ is a edge. Then $d(a,x) >3$, contradiction. $\square$ Now consider cases based on size of $\vert B \vert$. Case 1 : $\vert B \vert \ge n$ We count the total number of edges in the graph : There are $\vert A \vert$ edges from $A$ to $B$. There are $\tbinom {\vert B \vert}2$ edges from $B$ to itself. There are atleast $\vert C \vert$ edges from $C$ to $B$. There are atleast $\vert X \vert$ edges from $X$ to $C$. Hence we have : $$ \vert E(G) \vert \ge \vert A \vert + \binom {\vert B \vert}2 + \vert C \vert + \vert X \vert = 3n^2 + \binom {\vert B \vert}2 - \vert B \vert \ge 3n^2 + \binom n2-n = N$$ Where we used the fact that $\vert B \vert \ge n$. Hence we are done for this case. $\square$ Case 2 : $\vert B \vert <n$ We will use improved bounds for this case. Since maximum degree is $4n$, we have the estimates : $$ \vert A\vert + \vert C \vert \le \left(\vert B \vert \right) \left(4n+1- \vert B \vert \right) \le 3n^2-n-2$$$$ \vert X \vert = 3n^2 - \vert B \vert - \left( \vert A \vert + \vert C \vert \right) \ge 3n^2-(n-1)-(3n^2-n-2) =3$$ Now pick the vertex $x\in X$ such that the number of neighbors of $x$ in $C$ is minimum and let this value be $k$. We again count the edges : There are $\vert A \vert$ edges from $A$ to $B$. There are $\tbinom {\vert B \vert}2$ edges from $B$ to itself. There are $\vert B \vert$ edges from $N(x)$ to $B$ (to maintain the second claim). There are atleast $\vert C \vert - k$ edges from $C \setminus N(x)$ to $B$. There are atleast $k\vert X \vert$ edges from $X$ to $C$. This gives us: $$ \vert E(G) \vert \ge \binom {\vert B \vert}2 + \vert A \vert + \vert B \vert + \vert C \vert - k + k\vert X \vert$$$$ \implies \vert E(G) \vert \ge 3n^2-1 + \binom {\vert B \vert}2 + (k-1)(\vert X\vert -1)$$ Now we make two sub cases : Sub case 2.1 : $k=1$. Note that since the degree of every vertex in $X$ is at least $2$ and every vertex in $X$ has atleast one neighbour in $C$, we count $\frac {\vert X\vert}2$ more edges. This gives : $$ \vert E(G) \vert \ge 3n^2-1 + \binom {\vert B \vert}2 + \frac {\vert X \vert}2$$$$ \implies \vert E(G) \vert \ge 3n^2-1 + \binom {\vert B \vert}2 + \frac {3n^2 - \vert B \vert - \left(\vert B \vert \right) \left(4n+1- \vert B \vert \right) }2$$ It's easy to see that the RHS as a function of $\vert B \vert$ is minimized at $\vert B \vert = n + 0.75$ at which the function value is $>N$, so the conclusion follows. $\square$ Sub case 2.2 : $k>1$. We have : $$ \vert E(G) \vert \ge 3n^2-1 + \binom {\vert B \vert}2 + \vert X \vert - 1$$$$ \implies \vert E(G) \vert \ge 3n^2-2 + \binom {\vert B \vert}2 + 3n^2 - \vert B \vert - \left(\vert B \vert \right) \left(4n+1- \vert B \vert \right) $$ It's easy to see that the RHS is always $>N$ by a similar arguement as above, and so we conclude. $\square$