Double-tree shortcutting on the four-vertex square metric

The six stated distances are nonnegative and symmetric with $d(u,u)=0$; every distance between distinct vertices is $1$ or $2$, so for any three vertices with $u\mathrm{\ne }v\mathrm{\ne }w$ one has $d(u,v)+d(v,w)\ge 1+1=2\ge d(u,w)$, and inserting $v=u$ or $v=w$ gives the equality $d(u,w)=d(u,v)+d(v,w)$. The triangle inequality therefore holds and the data form a metric-TSP instance on four vertices.

The edge set $T=\{AB,BC,CD\}$ has $4$ vertices, $3$ edges, and forms the path $A-B-C-D$, hence is connected and acyclic, a spanning tree; its weight is $w(T)=1+1+1=3$. Every spanning tree of a four-vertex graph has exactly $3$ edges by [F2] and every edge length is at least $1$, so every spanning tree has weight at least $3$; therefore $T$ is a minimum spanning tree and $w(T)=3$.

Every tour is a cyclic ordering of the four vertices and consists of four edges, each of length at least $1$, so every tour has cost at least $4$; the cyclic ordering $A-B-C-D-A$ has cost $1+1+1+1=4$. Hence ${\mathrm{OPT}}_{\mathrm{T}\mathrm{S}\mathrm{P}}=4$.

Doubling the three tree edges produces the multigraph with edges $AB,BA,BC,CB,CD,DC$; it is connected and the degrees are $\mathrm{deg}(A)=2$, $\mathrm{deg}(B)=4$, $\mathrm{deg}(C)=4$, $\mathrm{deg}(D)=2$, all even. The closed walk $A-B-C-D-C-B-A$ uses each of the six edges exactly once, so it is an Euler circuit of the doubled multigraph, with total cost $1+1+1+1+1+1=6=2w(T)$.

The vertices occur for the first time along this walk in the order $A,B,C,D$, so first-visit shortcutting yields the tour $A-B-C-D-A$. Its segments are the walks $A\to B$, $B\to C$, $C\to D$ of length $1$ each and the return segment $D\to C\to B\to A$ of length $3$; the shortcut edge $DA$ has length $1\le 3$, the sum of the segment lengths, so the shortcut tour has cost $1+1+1+1=4\le 6=2w(T)$, and by step 2.2 it equals ${\mathrm{OPT}}_{\mathrm{T}\mathrm{S}\mathrm{P}}$.

The computed tree satisfies $w(T)=3\le 4={\mathrm{OPT}}_{\mathrm{T}\mathrm{S}\mathrm{P}}$, in agreement with the minimum-spanning-tree lower bound, and the shortcut tour has cost $4\le 6=2w(T)\le 2{\mathrm{OPT}}_{\mathrm{T}\mathrm{S}\mathrm{P}}=8$, so this instance realizes the double-tree guarantee of [F4] with a strict improvement over the doubled walk.