Let $T$ be the unique minimum spanning tree. If $e=ab$ is an edge outside $T$, adding it creates a unique graph cycle consisting of $e$ and the tree graph path $P_T(a,b)$. Every edge $f$ on that graph path has $w(f)<w(e)$: otherwise the distinct weights would give $w(f)>w(e)$, and replacing $f$ by $e$ would produce a cheaper spanning tree. This is the minimum spanning tree cycle property in exchange form.

By the domination inequality in (i), it follows more strongly thatNow consider any simple graph path $P$ from $v$ to $u$ that is not the tree graph path. It must use an edge outside $T$. Replace every such edge by the corresponding tree graph path. Each replacement strictly reduces length and produces a walk entirely in $T$. Removing any repeated-vertex excursions leaves the unique tree graph path $P_T(v,u)$ and can only reduce length further. ThereforeSo every root-to-vertex graph path in $T$ is the unique shortest graph path in $G$, andThe argument works for every choice of root $v$.

By (i), two simple graph paths with different edge sets have different lengths. In particular two distinct simple graph paths from the fixed root $v$ to the same graph vertex $u$ have different edge sets, so there is a unique shortest graph path from $v$ to each $u$. Positive weights ensure that a shortest walk has no repeated graph vertex: removing a graph cycle strictly reduces its length.

For each $u\ne v$, take the final edge of its unique shortest graph path. Every initial segment of a shortest graph path is itself shortest, since replacing it by a shorter one would shorten the whole route. Thus these edges agree with the graph paths' unique predecessors. Following a predecessor strictly decreases $d_G(v,u)$, so no predecessor graph cycle is possible, and all graph vertices eventually connect to $v$. They form a shortest-path tree. Every other such tree would have to use the same unique root-to-vertex graph paths, provingLiteral wording qualification. “Any two paths” needs a convention. Reversing an undirected graph path preserves its edge set and length; distinct zero-edge graph paths at different graph vertices also have length zero. Thus the unrestricted statement is false if these count as different graph paths. The proved edge-set assertion, and in particular uniqueness for graph paths with the same ordered endpoints, is exactly what is needed for the deduction. Arbitrary walks are not included.

Assume throughout (c) that the graph is finite and connected, as needed for the asserted spanning trees. List its edge weights as $w_1<\cdots <w_m$. The stated separation implies $w_{j+1}>2w_j$, so for every $k$,Thus the weights form a superincreasing sequence. If $A,B$ are distinct edge sets, let $e$ be the heaviest edge in their symmetric difference. Suppose $e\in A$. All other uncancelled edges are lighter, soTherefore different edge sets have different total costs. In particular all distinct spanning trees have different costs. Since a finite connected graph has at least one spanning tree and only finitely many choices,This domination of every collection of smaller edges will also be used in (iii).

At weight $x+1/2$, column $x$ is considered just after horizontal row $x$. At this point its first $x$ graph vertices already lie in the component built so far, while graph vertices above them in that column are isolated. Consequently vertical edges with $y<x$ create a graph cycle, while those with $y\ge x$ attach the isolated graph vertices in a chain:Together with the horizontal rule this gives an induction on the alternating row and column stages and justifies the component description used in both numbered answers. The vertical contribution to the minimum spanning tree cost is

At weight $y$ the edges considered are precisely the horizontal edges in row $y$. For $y=1$ all $n$ graph vertices in that row are isolated, so all $n-1$ edges are accepted. For $y\ge 2$, the first $y-1$ graph vertices in that row already belong to the one component built by earlier stages, because vertical columns $1,\dots ,y-1$ have already been processed. The other graph vertices are isolated. Thus the edges with $x<y-1$ would create a graph cycle, and all the edges with $x\ge y-1$ are accepted, successively attaching the remaining graph vertices. The rule isThe selected edges of equal weight have no cycles after the existing component is contracted, so tie ordering does not affect this conclusion. Their combined contribution to the minimum spanning tree cost is

Substitute $\hat{u}=e^{-b(t)s^2}$ into the transformed partial differential equation. Comparing coefficients gives $b^{\prime }=1-2b$, $b(0)=0$, whenceThe stated Gaussian Fourier transform pair, with its inverse factor $1/(2\pi )$, givesThis is a normal distribution density with mean zero and variance $1-e^{-2t}$. Its total integral is one. As $t\downarrow 0$ it converges to $\delta$ in the sense of distributions, while as $t\to \infty$ it tends to the standard normal distribution density. This is the transition density from zero of the Ornstein-Uhlenbeck process with drift $-x$ and diffusion coefficient $\sqrt{2}$.

Use the Fourier transform convention $\hat{u}(s,t)={\int }_{\mathbb{R}}{e}^{-isx}u(x,t)dx$. Then $\widehat{u_{xx}}=-s^2\hat{u}$ and $\widehat{xu}=i{\partial }_s\hat{u}$, soThus the transformed partial differential equation and initial condition areThe last equality is the Fourier transform of the Dirac delta distribution. The two terms in ${\partial }_x(xu)=u+x{u}_x$ must be transformed together; dropping $u$ would give the wrong equation.

Use the causal convolution $(f_0\ast f_1)(x)={\int }_0^x{f}_0(t)f_1(x-t)dt$. The convolution theorem for Laplace transforms and (i) giveSince $\mathcal{L}(\cos x)=p/(p^2+1)$, uniqueness of the Laplace transform yieldsAt $x=0$ the right side is $1-1=0$, agreeing with the empty convolution integral. Identification of $f_0$ as a Bessel function is unnecessary.

Write $F_j(p)=\mathcal{L}{f}_j(p)$, using the square-root branch positive on real $p>0$. Integrating the differential equation and using boundedness at zero givesThe integration constant is zero since $x{f}_1(x)\to 0$. Continuity of $f_0$ then shows $f_1(x)=O(x)$, so $f_1$ extends continuously with $f_1(0)=0$.

The Laplace transform of a derivative and differentiation under the integral sign giveIntegrating and using $F_1(p)\to 0$ as real $p\to \infty$ fixes the constant:The initial value theorem for Laplace transforms gives $f_0(0)={\lim }_{p\to \infty }p{F}_0(p)=1$. It is tempting to apply the derivative rule immediately to $f_0$, but its stated regularity is only continuity. To justify that step, define $h(x)=1-{\int }_0^x{f}_1(t)dt$. ThenUniqueness of the Laplace transform gives $h=f_0$, and hence $f_0$ is continuously differentiable and

Multiplication of a distribution by a smooth function is defined by moving that function onto the test function. The Dirac delta multiplication identity givesIn fact $x^2\delta$ is the zero distribution, independently of the special positivity assumptions on $\varphi$.

Suppose $D{F}_x$ were invertible at some $x\in \Omega$. The inverse function theorem supplies a neighborhood $V$ of $x$ for which $F(V)$ is a nonempty open subset of ${\mathbb{R}}^2$. But $F(V)\subset M$, and a one-dimensional embedded submanifold of ${\mathbb{R}}^2$ has empty interior. To see this last assertion, a slice chart for an embedded submanifold takes $M$ locally into a coordinate line; a coordinate line cannot contain an open plane neighborhood, and a chart preserves openness. This is a contradiction.

Thus $D{F}_x$ is singular everywhere. Part (c)(i) strengthens singularity to $D{F}_x=0$ everywhere. By (b) and connectedness of $\Omega$,The special form of the Jacobian matrix is essential: an arbitrary differentiable map can have nonconstant image in a curve with derivative of rank one.

Write $a={\partial }_1{f}_1={\partial }_2{f}_2$ and $b={\partial }_2{f}_1=-{\partial }_1{f}_2$. The Cauchy-Riemann equations giveConsequentlyEquivalently, it is singular exactly when all four partial derivatives vanish. The sum of squares is over $\mathbb{R}$, so no cancellation is possible.

No. On $\Omega ={\mathbb{R}}^2$ letIt is a bijection onto ${\mathbb{R}}^2$, with inverse $(u,v)\mapsto (\sqrt[3]{u},v)$. Nevertheless $D{F}_{(s,t)}=\mathrm{diag}(3s^2,1)$ is singular whenever $s=0$. Set-theoretic invertibility, even together with a continuous inverse, does not force invertibility of the total derivative. If the inverse were assumed differentiable, the chain rule applied to $F^{-1}\circ F$ would force both derivatives to be invertible; that stronger assumption is absent here.

Take $\Omega ={\mathbb{R}}^2$ andIts Jacobian matrix and determinant areThus its total derivative is invertible everywhere, and the inverse function theorem makes it locally invertible. But $F(s,t+2\pi )=F(s,t)$, so it is not injective and has no global inverse on its image. The domain is open and connected as required.

Choose a point $A$ off $L$, then a point $B$ on $A{R}_2$ distinct from $A,R_2$. PutThese four points form a projective frame: $A,B$ lie off $L$, and $AB=A{R}_2$ meets $L$ at neither $R_0$ nor $R_1$. Form, using only joins and intersections,Here the point called $Q_1$ in (i) is $R_2$, while $Q_3$ is $R_3$. Thus (i) gives $(R_0{R}_1:R_3{R}_2)=-1$. Interchanging the last two arguments reciprocates the cross-ratio, soAll auxiliary choices are possible over a field of characteristic zero, which is infinite. Uniqueness from (a)(ii) shows that the final point is independent of those choices. The picture uses an affine chart in which every relevant intersection is finite; parallel-line exceptions in another chart are ordinary intersections on the projective line at infinity.

The four points form a projective frame: no three are collinear. By the allowed uniqueness theorem and cross-ratio invariance, useIntersecting the indicated projective lines givesA point of $Q_0{Q}_2$ has coordinates $[a:b:a+b]$. Intersecting with $P_0{P}_1$, whose equation is $z=0$, gives $Q_3=[1:-1:0]$. On that line use its first two homogeneous coordinates. The cross-ratio from (a)(ii) isThe characteristic of a field being zero ensures that $Q_3\ne Q_1$. The construction is the diagonal-point property of a complete quadrangle, producing harmonic conjugate points.

Choose nonzero vectors $p_i\in {\mathbb{F}}^2$ representing $P_i$, and write $[u,v]=\det (u,v)$. Use the cross-ratio conventionDistinctness makes the denominator nonzero. Every rescaling of a representative occurs once in numerator and denominator, so the value depends only on the projective points. Swapping both pairs simply exchanges the numerator's factors and the denominator's factors:Under an invertible linear map $A$, $[Au,Av]=\det (A)[u,v]$. Two factors of $\det (A)$ occur above and below the fraction, proving projective transformation invariance.

Finally choose homogeneous coordinates making $P_0=[1:0]$, $P_1=[0:1]$, $P_2=[1:1]$. This normalization exists by the allowed theorem about a projective frame. A point distinct from $P_0$ is uniquely $[t:1]$, and the displayed cross-ratio is $t$. Thus equality of the two cross-ratios forces equal coordinates andThis also shows that for fixed first three distinct points the fourth point is determined by its cross-ratio.