Thanks to your very well-written question, which makes my answer writing a real pleasure.
Claim I: "it is unnecessary to add edges from comparing non-adjacent words."
Let us take a look at how the algorithm pulls information when comparing two words, which is "iterating through their characters, and finding the first pair of characters which differ". Then it obtains the requirement "the former string's character precedes the latter string's character". Use $R_{i,j}$ to denote the requirement thus obtained from two words word[i]
and word[j]
. In term of binary relation, $R_{i,j}$ can be expressed in the form $\alpha<\beta$ for some character $\alpha, \beta$. Note $R_{i,j}$, if satisfied, determines word[i]
and word[j]
must be arranged in the given order as in the array word
. In other words, any strict partial order on the characters that includes $R_{i,j}$ must sort word[i]
and word[j]
in the order as given in the array word
.
Let $O$ be the minimum strict partial order on the characters that includes $R_{1,2}, R_{2,3}, \cdots, R_{n-1,n}$. Then any arrangement of words must put word[2]
after word[1]
, word[3]
after word[2]
, ..., word[n]
after word[n-1]
if that arrangement is in accordance with $O$. That is, all words must be arranged in the order exactly as given in the array word
. Since any desired dictionary order, a.k.a. lexicographic order, (which can be obtained by a topological sort according to those n-1 requirements), is a strict total order (and hence also a strict partial order) that extends $O$, no more information is needed to order any pair of words.
Claim I is proved in the sense of the last statement.
Lemma: Let $<_1$ be a strict partial order on a set $S$ and $a,b\in S$. If $a\not<_1b$, (which does not implies $b<_1 a$), then there is a strict partial order $<_2$ on $S$ that extends $<_1$ with $b<_2 a$.
The lemma says that if one element is not defined as smaller than another element in a strict partial order, then we can assign the relationship between those two elements the other way around without causing conflict. It will be clear soon that this lemma is the crux of this answer.
In case that you are not familiar with the terminologies of partial order, here is an equivalent version in term of directed graph. Given a directed acyclic graph whose transitive closure has no edge going from one particular vertex to another vertex, if you add an edge that goes from the latter vertex to the former vertex, the resulting graph will still be acyclic. (One can also note that whether a directed graph is acyclic or not will not be changed if we take a transitive closure of the graph. This transitive closure corresponds to the transitivity of the strict partial order.)
I will leave the simple proof of this lemma to you.
Claim II: "Comparing any two words which are not adjacent will not yield any new information."
Let us continue to use the terms introduced in the proof of Claim I. Before we proceed to a proof, let us define what is existing information. The existing information is all requirements $R_{i,i+1}$ for $1\le i\le n-1$ or, what is equivalent, $O$, the minimum strict partial order which includes those requirements (and their implications), which is able to determine the order relationship of any pair of words in the array word
.
For the sake of contradiction, suppose comparing word[i]
and word[j]
could yield a requirement that can be considered as new information, i.e., assuming this new requirement is $\alpha'<\beta'$ for some character $\alpha', \beta'$, that relationship between $\alpha'$ and $\beta'$ is not in $O$. By the above lemma, we can extends $O$ with $\beta'<\alpha'$ to obtain another strict partial order $O'$. Note that $O'$ requires word[i]
and word[j]
be arranged in the reverse order of how it appears in array word
, which contradicts our conclusion above that any strict partial order that extends $O$ must put word[i]
and word[j]
in the same order as it appears in array word
.
Claim II is proved.
For an even higher level of rigor, we should also note explicitly what happens when two words, one of which is a prefix of the other one, are compared. We should also mention explicitly the case when the initial array word
is not consistent, such as ['a', 'b', 'a']
. We should flesh out more details about the strict partial orders. I will not go into such detail, assuming the above explanation is enough to enable readers who are able to read thus far to fill in the details if needed.