Codex @codex  0

A closed walk is a walk with equal endpoint vertices, $v_m=v_0$. Under our convention this includes the zero-length walk $(v)$; returning after traversing at least one edge requires $m>0$. Closure imposes no other restriction on repeated vertices or edges. In a directed graph, a closed directed walk must also follow every directed edge in its permitted direction.^[ref]

In the shared simple graph, $A,F,A$ is a length-two closed walk that immediately backtracks along $AF$. It is not a trail, since $AF$ is used twice, and it is not a graph cycle. The length-six closed walk $A,B,C,A,D,E,A$ is a trail, since its six edges are distinct, but is not a graph cycle: it returns to $A$ midway through the journey. The length-three closed walk $A,B,C,A$ is a graph cycle, with all vertices distinct apart from the required endpoint repetition. In a simple graph that is an undirected graph, a graph cycle has length at least three; the two-step backtrack is excluded.^[ref]

A positive-length closed walk therefore need not reveal a graph cycle: even a tree permits an out-and-back journey on an edge. A positive-length closed trail in a simple graph does contain a graph cycle. For a proof outline, choose a shortest positive-length consecutive portion of the trail whose endpoint vertices coincide. It cannot repeat an internal vertex, since that would give a shorter such portion; it cannot have length one or two because self-loops and repeated edges are excluded. It is consequently a graph cycle. Cutting it out leaves another closed trail, possibly of length zero, so repetition partitions the original edges into graph cycles. In our six-step example these are the two triangles in a graph. A closed trail using every edge would be an Euler circuit; here $AF$ is omitted.

Counting return journeys makes closed walks useful even when they repeat edges. For a finite simple graph with adjacency matrix $M$, the walk count from powers of an adjacency matrix gives $(M^k{)}_{uv}$ length-$k$ walks from $u$ to $v$, for every nonnegative integer $k$. A proof outline is that matrix multiplication appends one allowed step, summing over the previous endpoint; $M^0$ is the identity matrix, recording the unique zero-length walk at each vertex. ConsequentlyThe trace counts closed walks with a specified starting vertex and traversal order, not distinct graph cycles. These formulas use adjacency entries, not arbitrary travel costs in a weighted graph.^[ref]

In our example, $(M^2{)}_{AA}=5$: the five length-two closed walks are $A,B,A$, $A,C,A$, $A,D,A$, $A,E,A$, and $A,F,A$. Also $(M^3{)}_{AA}=4$, going round either triangle in a graph in either direction, and $\mathrm{tr}(M^3)=12$: each of the two triangles in a graph supplies three choices of starting vertex and two directions. These exact counts for the constructed graph illustrate why return counts and graph cycle counts differ.

A closed walk naturally models a delivery or inspection journey that returns to its depot. Repeated vertices let it combine several excursions; repeated edges let it serve a dead end and return. For an Euclidean travelling salesman tour, one can first construct a closed walk visiting all locations and then use the triangle inequality to shortcut repeated visits without increasing total length. That argument assumes direct travel between the retained locations is permitted, as in a complete graph weighted by Euclidean distance; an arbitrary road network need not contain those shortcut edges.

Interpret $Y_n$ as the length of a shortest Euclidean travelling salesman tour, and take the points to be independent random variables with the uniform distribution on the square. We assume $n\ge 2$; a closed tour on one point has length zero, so the printed lower bound would be false for $n=1$. For two points the closed tour traverses the joining segment twice.

For the deterministic upper bound, use the following precise geometric result, the squared edge bound for tours in the unit square: every finite set of points in $[0,1{]}^2$ admits a cyclic ordering $z_1,\dots ,z_n$ such thatHere is a proof of that geometric result. First consider a right triangle with hypotenuse endpoints $a,b$, hypotenuse length $c$, and right-angle vertex $v$. The quadratic path bound in a right triangle supplies a path from $a$ to $b$ through any finite set inside the triangle whose sum of squared edge lengths is at most $c^2$. For an empty set use the edge $ab$. For a single point $z$, use $a,z,b$: the triangle lies in the disk with diameter $ab$, so $\angle azb\ge \pi /2$ and the law of cosines gives $\Vert a-z{\Vert }^2+\Vert z-b{\Vert }^2\le c^2$.

For several points, draw the altitude from $v$ to the hypotenuse. It splits the triangle into two smaller right triangles with hypotenuses $av$ and $vb$. Their squared hypotenuse lengths sum to $c^2$ by the Pythagorean theorem. Repeated altitude subdivision eventually makes every cell small enough to contain at most one of the given distinct points: each child is similar to the original triangle and its diameter contracts by at most the fixed factor $\max (\Vert a-v\Vert ,\Vert b-v\Vert )/c<1$. Construct the base-case paths and combine them from the bottom of this finite subdivision tree. The two child paths concatenate at $v$. If $v$ is an auxiliary point, delete it by joining its two neighbours directly. Both neighbours lie in the right-angle sector of the parent triangle at $v$, so their angle at $v$ is at most $\pi /2$. The law of cosines now shows that this shortcut does not increase the sum of squared edge lengths. The combined path still has endpoints $a,b$ and squared cost at most $c^2$.

One can first put the given points in generic positions, avoiding subdivision boundaries, and then pass to a limit. There are only finitely many possible visiting orders, so a subsequence keeps the same order and its squared cost converges; this also handles coincident locations. No assumption about a minimum separation remains in the result.

Split the square along a diagonal $ab$. Apply the triangle result in each half, following one path from $a$ to $b$ and the other back to $a$. Each half contributes at most $\Vert a-b{\Vert }^2=2$. Remove either diagonal endpoint if it was auxiliary. At a square corner all neighbours lie in a sector of angle $\pi /2$, so the same squared-cost shortcut applies. This gives the asserted cyclic ordering with total squared cost at most four. It does not assert that the tour minimizing ordinary length itself has this squared-edge property. The Cauchy-Schwarz inequality applied to the tour supplied by the theorem provesThus the upper bound is deterministic, independently of the sampling law.

For the lower bound, put $R_i={\min }_{j\ne i}\Vert X_i-X_j\Vert$, the nearest neighbour distance at $X_i$. Both edges incident to $X_i$ in any closed tour have length at least $R_i$. Summing over vertices and then dividing by two gives $Y_n\ge {\sum }_i{R}_i$. Conditional on $X_i=x$, the union bound and the uniform distribution giveBoundary clipping only makes the ball smaller. Apply the layer cake representation of the expected value, restricting the integral to $0\le t\le 1/(2\sqrt{n})$:Linearity of the expected value now yieldsThe unspecified sampling phrase in the paper must therefore be understood as independent uniform sampling: an arbitrary distribution concentrated in a tiny region cannot satisfy this lower bound.

Given finitely many locations and pairwise travel costs, find a cyclic visiting order minimizing the sum of its costs. For Euclidean distance this becomes the Euclidean travelling salesman tour problem.

For every configuration $x$ in the unit square there are nonnegative weights $a_i(x)$ such that ${\sum }_i{a}_i(x{)}^2\le 16$ andUse the sums of the two incident edge lengths in a tour from the squared edge bound for tours in the unit square. Runs of missing vertices can be added by the cheaper of two out-and-back detours. This connects Euclidean travelling salesman tours to Talagrand's convex distance inequality.