Prove that there exists a graph with these points such that....

[hitemup]

Homework Statement

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 10\sqrt{n}$$
Prove also the ##10## in the inequality can't be replaced with ##1##.

Homework Equations

These may be relevant:

https://en.wikipedia.org/wiki/Trave..._length_for_random_sets_of_points_in_a_square

https://math.stackexchange.com/ques...istance-between-two-random-points-in-a-square

The Attempt at a Solution

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?

 

[haruspex]

To get a bit of insight into the nature of the inequalty, I suggest starting with the second part - find a family of sets of vertices such that the total edge length to get them connected exceeds √n.

 

[haruspex]

I should use Erdös-Renyi random graph model to prove the existence of a connected graph.

Should I look for the expected value of the total length of nnn points maybe?

I do not see how a probabilistic argument is going to work. Sets of points that make finding a suitable set of edges hard may be quite rare, and the average distance sum may bear little relationship to the minimum distance sum.

Start by considering what a set of edges of minimum total length (given the connectedness condition) would look like,