証明自体は仮定からほぼほぼ自明に近いのですが，証明するのに少し考えてしまったので忘れないようにメモ．
証明
ユークリッド平面上の 4 点(A, B, C, D)を考える．ここで A→B→C→D(経路1) は経路の交差がなく，A→C→B→D(経路2)は A→C(AC) と B→D(BD) が交差しているとする．AC と BD の交点を X とする．経路1と経路2の経路長をそれぞれ $d_1$ と $d_2$ とすると， $$ \begin{array}{lll} d_1 & = & AC + BC + BD \\ & = & (AX + XC) + BC + (CX + DX) \\ & = & (AX + BX) + BC + (CX + DX) \\ d_2 & = & AB + BC + CD \\ \end{array} $$ となる．ここで，三角形 AXB を考えると，三角不等式より $$ \begin{array}{lll} AX + BX \geq AB \end{array} $$ が成り立つ．これは三角形 CXD でも同様に成り立つから $$ \begin{array}{lll} CX + DX \geq CD \end{array} $$ となる．従って，$d_1$ と $d_2$ の大小関係は $$ \begin{array}{lll} d_1 & = (AX + BX) + BC + (CX + DX) \\ & \geq AB + BC + (CX + DX) \\ & \geq AB + BC + CD \\ & = d_2 \end{array} $$ となる．よって，$d_1$ は最短経路ではない．(証明終)
こういう証明をぱっとできるようにならないとですね．