Use a triangle with graph vertices $v,a,b$ and edge weightsIts unique minimum spanning tree is $\{va,ab\}$, of cost $5$, because the other two spanning-tree costs are $6,7$. In this tree the $v$-to-$b$ graph path has length $2+3=5$, whereas the edge $vb$ gives length $4$ in the original graph. ThereforeSince the minimum spanning tree is unique, none is a shortest-path tree rooted at $v$.

For a finite connected graph, a spanning tree contains every graph vertex and is connected and acyclic. A minimum spanning tree minimizes ${\sum }_{e\in E(T)}w(e)$ over all such trees. A shortest-path tree rooted at $v$ is a spanning tree whose unique $v$-to-$u$ graph path has length $d_G(v,u)$ for every graph vertex $u$. Here the weighted path length is the sum of its edge weights. The two optimizations generally differ, as (b) shows. Connectedness is needed for either spanning-tree object to exist.

For the grid, Kruskal's algorithm examines edges in nondecreasing order of weight and accepts an edge exactly when it joins two different components of the current forest. The weights are encountered in the orderThe horizontal and vertical acceptance rules are detailed in the two numbered subanswers. Together they produceThere are $(n-1)(n+2)/2$ horizontal and $n(n-1)/2$ vertical edges, totaling $n^2-1$. Every accepted edge attaches a previously isolated graph vertex to the component already built, so the result is connected and acyclic. The correctness theorem for Kruskal's algorithm, which follows from the minimum spanning tree cut property, proves minimality. Its total cost isFor $n=1$ the tree has one graph vertex, no edges and cost zero. The source's numbered items specify the two edge types; the following subanswers record their contributions to the algorithm.

Put $f(\varphi )=dx/d\varphi$. Since $\sin ((2\pi -\varphi )/2)=\sin (\varphi /2)$, both $f(2\pi -\varphi )=f(\varphi )$ and $y(2\pi -\varphi )=y(\varphi )$. Using $x(2\pi )=1$ in the integral for $x$ givesHence the physical track $(x,-y)$ is symmetric about $x=1/2$, with $x(\pi )=1/2$. For $0<\varphi <2\pi$, $dx/d\varphi >0$, andis positive before $\pi$ and negative after $\pi$. Therefore the physical height $-y$ has its unique minimum at $x=1/2$, withThe depth $y$ has a maximum there. This proves the intended claim for every finite-time member $L>1$; $L=1$ has the degeneracy described in (a).

With $H>0$, setThen the first integral gives $1/\sqrt{1+y^{\prime 2}}=s$. On the descending and ascending halves of the physical track choose respectively $0<\varphi <\pi$ and $\pi <\varphi <2\pi$, so that $y^{\prime }=\cot (\varphi /2)$. Solving for $y$ givesThe unsquared equation requires $1-bs>0$. At $s=1$ this says $b<1$; it is not permissible to retain other values merely because the displayed formula for $y$ has a squared denominator.

For completeness, the Euler-Lagrange equation also gives $y^{\prime \prime }=(A^{\prime }(y)/A(y))(1+y^{\prime 2})<0$. Thus $y^{\prime }$ decreases through zero exactly once, so the chosen parameter runs through the whole single arch without an extra branch. Differentiating the formula for $y$ and dividing by $y^{\prime }=\cot (\varphi /2)$ gives, continuously also at $\varphi =\pi$,Using $x(0)=0$ yieldsSince $\sqrt{1+y^{\prime 2}}=1/\sin (\varphi /2)$, the arc length is obtained by cancelling one factor of $\sin (\varphi /2)$ in $dx/d\varphi$. The conditions $x(2\pi )=1$ and $S=L$ becomeThese determine a unique parameter pair for each $L>1$. To see uniqueness, regard $L$ as the expected value of $1/s$ under a probability density function proportional to $s^2/(1-bs{)}^3$ on $0<u<2\pi$. Differentiation under the integral sign gives the covariance identityThe first argument decreases with $s$ and the second increases. The strict sign follows by applying $(f(s)-f(t))(g(s)-g(t))<0$ to two independent unequal values and averaging; the integrable endpoint singularity of $1/s$ causes no problem. As $b\uparrow 1$, the weight concentrates at $s=1$, so $L\downarrow 1$. As $b=-k\to -\infty$, endpoint estimates give numerator $\sim 2/k^2$ and denominator $\sim 4\log k/k^3$, so $L\sim k/(2\log k)\to \infty$. Continuity then covers every $L>1$. At $b=0$ one recovers the cycloid and $L=4/\pi$.

Smoothness qualification. Near $\varphi =0$,and the other endpoint has $y^{\prime }\to -\infty$. These are smooth graphs on $0<x<1$, not $C^1$ graphs on the closed interval. Indeed a finite endpoint slope would make the conserved $H$ diverge as $y\to 0$. The travel time remains finite becauseThus the printed phrase “smooth solution” must be understood on the interior, with improper endpoint limits. The variational calculation supplies necessary stationary arches; it does not by itself prove global minimality in every larger class of tracks.