Is there a basic proof that there exists some edit distance between two strings?
Given two strings $v,w \in \Sigma^*$ with $m = |v| \geq |w| = n$ (w.l.o.g.), align them like so:

$\qquad\displaystyle\begin{array}{ccccccc}
v_1 &amp; v_2 &amp; \dots &amp; v_n &amp; v_{n+1} &amp; \dots &amp; v_m \\
w_1 &amp; w_2 &amp; \dots &amp; w_n &amp; - &amp; \dots &amp; -
\end{array}$

This alignment implies an edit distance of

$\qquad\displaystyle 0 \leq d_{\text{edit}}(v,w) \leq d_{\text{Ham}}(v,w[1..n]) + (m-n)$.

In particular, there is an alignment for any two strings. Note furthermore that there are only finitely many alignments of $v$ and $w$ (we forbid columns $\genfrac{}{}{0pt}{}{-}{-}$), so one with minimal score (which is the edit distance) must exist.

Hence, any two strings have finite edit distance and the graph is connected.