Cfrgtkky

Let us have $n geq 3$ points in a square whose side length is $1$. Prove that there exists a graph with these points such that $G$ is connected, and
$$sum_{{v_i,v_j} in E(G)}{|v_i - v_j|} leq 10sqrt{n}$$
Prove also the $10$ in the inequality can't be replaced with $1$.

I think I should use Erdös-Renyi random graph model to prove the existence of a connected graph. In that model, if an edge appears with probability $p$, then, for example, a particular connected graph with $n-1$ edges appear with $p^{n-1}(1-p)^{binom{n}{2} - (n - 1)}$. Is this enough to show a connected graph exists since this probability should be greater than zero? Regardless of this, I found proofs showing that the expected distance between two points picked on a unit square is around $0.52$, but I think that is not useful. Should I look for the expected value of the total length of $n$ points maybe?

I was trying to prove the upper bound $2sqrt{n} + 2$ on TSP Path length in the following link before an answer came. I'll leave it here in case it works for somebody.

https://en.wikipedia.org/wiki/Travelling_salesman_problem#TSP_path_length_for_random_sets_of_points_in_a_square

A random graph won't help you. After all, it is clear that some connected graph exists (e.g., the complete graph), but we might need to derive bounds for the minimal spanning tree.

For some $cge 1$ (in the problem statement, $c=10$), we may want to prove that the total edge length of a minimal spanning tree of any set of $n$ points in the unit square is $le csqrt n$. We do this by induction on $n$, noting that $n=0$ and $n=1$ the total length is trivially $=0$, and for $n=2$, the worst case length is $sqrt 2$.
For $n=3$, the shortest tree we can find for three points in three vertices of the square is $2$, so we certainly need $cgefrac 2{sqrt 3}>1$. This already answers the second part of the question.

Let $c=2sqrt 2$. Then

Claim. $n$ points in the unit square are the vertices of a connected graph of total edge length $ellle csqrt n$.

Proof. The claim is trivially true for $n=0$ and for $n=1$.
Suppose we are given $nge 2$ points in the unit square and know that the bound holds for all smaller sets of points.
Let $k=lfloor sqrt nrfloor$ and tile the square into $ktimes k$ smaller squares.

If $n=k^2$, it may happen that each tile contains exactly one of the points. We can then join the point by $k^2-1$ times joining points in adjacent tiles (e.g., in a snake-like pattern across the tiles). The edges used herein are all $le frac{sqrt 5}k$ ($=$the diagonal through a rectangle formed from two adjacent tiles), thus giving a total length of
$$ ellle(k^2-1)frac{sqrt 5}k<ksqrt 5=sqrt 5sqrt n<csqrt n.$$

In all other arrangements of $n^2$ points, as well as when $n>k^2$ (pigeon-hole!), we find at least one tile with at least two of the points in it. Ignore one of these points, then use the induction hypothesis to join the other $n-1$ points with edges of total length $le csqrt {n-1}$, and join the ignored point to a "tile-mate" with an additional edge of length $le frac {sqrt 2}k$ ($=$the diagonal of a tile) for a total length of
$$begin{align}ell&le csqrt {n-1}+frac{sqrt 2}{ k}\
&=csqrt n-frac c{sqrt{n-1}+sqrt n}+frac{sqrt 2}k\
&<csqrt n-frac{c}{2sqrt n}+frac{sqrt 2}k\
&le csqrt n-frac{c}{2sqrt n}+frac{sqrt 2}{sqrt n}\
&=csqrt n.end{align}$$
Hence the claim follow. $square$

We have already seen above that the claim becomes false for $n=3$ if we let $c=1$.
But there are also arbitrarily large counterexamples: Consider $n=2k^2$, and the $n$ points $(frac i{2k-1},frac j{2k-1})$ with $0le ile 2k-1$, $0le jle 2k-1$, $2equiv jpmod 2$. Then any two of these are at least $frac{sqrt 2}{2k-1}$ apart, and we need $n-1$ edges, thus the length of any connecting graph is
$$ell ge (2k^2-1)frac{sqrt 2}{2k-1}=ksqrt 2+underbrace{frac{1-frac 1k}{2-frac 1k}sqrt 2}_{to frac1{sqrt 2}}>sqrt n.$$

We can try to be more systematic: Cover each of the $n$ points with a disk of radius $r$. Then all these disks are within the square obtained by extending the unit square by $r$ in each direction. If the disks are disjoint, they cannot beat the densest packing, i.e.,
$$ npi r^2le frac{pi}{2sqrt 3}cdot (1+2r)^2,$$
or:
$$ (2sqrt 3 n-4) r^2-4r-1le 0.$$
If we let $r=frac a{sqrt n}$ for some fixed $a>frac 1{sqrt{2sqrt 3}}$, this condition amounts to
$$2sqrt 3a^2-1-frac {4a^2}n+frac{4a}{sqrt n}le0 $$
and is false for all sufficiently large $n$. We conclude that for all $ngg 0$, we find two points if distance $le frac{2a}{sqrt n}$.
Thus if we pick $ell_0$ such that $ellle ell_0+csqrt n$ holds for all small $n$, we can use induction like above for larger $n$ and show
$$ ell le ell_0+csqrt{n-1}+frac{2a}{sqrt n}le ell_0+csqrt n$$
provided
$$ frac{2a}{sqrt n}le c(sqrt n-sqrt{n-1})=frac{c}{sqrt n+sqrt{n-1}}$$
for which
$ cge 4a$, so ultimately
$$ c>frac 4{sqrt{2sqrt 3}}approx 2.1491398636470838391066763134118611543.$$
is sufficient.
This improves the above result to

Claim 2. There exists $ell_0$ such that for all $n$, any $n$ points in the unit square are the vertices of a connected graph of total edge length $ellle ell_0+2.14914sqrt n$. $square$

Since the constant $frac 4{sqrt{2sqrt 3}}$ stems right from the densest disk packing, I guess that it it is indeed the infimum of all factors before $sqrt n$ that can be used in claim 2. I.e.,

Conjecture. Let $c<frac 4{sqrt{2sqrt 3}}$ and $ell_0>0$. Then there exists $ninBbb N$ and $n$ points in the unit square such that the minimum spanning tree of these points hast total edge length $>ell_0+csqrt n$.