Can the sorting of a list be verified without comparing neighbors? A $n$-item list can be verified as sorted by comparing every item to its neighbor. In my application, I will not be able to compare every item with its neighbor: instead, the comparisons will sometimes be between distant elements. Given that the list contains more than three items and also that comparison is the only supported operation, does there ever exist a "network" of comparisons that will prove that the list is sorted, but is missing at least one direct neighbor-to-neighbor comparison?

Formally, for a sequence of elements $e_i$, I have a set of pairs of indices $(j,k)$ for which I know whether $e_j &gt; e_k$, $e_j = e_k$, or $e_j &lt; e_k$. There exists a pair $(l,l+1)$ that is missing from the set of comparisons. Is it ever possible, then, to prove that the sequence is sorted?
It is impossible. Suppose that you have the result of all comparisons except for the pair $(i,i+1)$. Then you wouldn't be able to distinguish between the following two cases:
$$
1,2,\ldots,i-1,i,i+1,i+2,\ldots,n \\
1,2,\ldots,i-1,i+1,i,i+2,\ldots,n
$$