CJam, 14 13 12 bytes
r$r$.-:)3,-!
Try it online! or verify all test cases at once.
Algorithm
Let s and t be two sorted words of the same length. For s and t to be lexicographically adjacent (LA), it is necessary and sufficient that all pairs of its corresponding characters are also LA.
The condition is clearly sufficient for all words, and necessary for words of length 1.
Now, assume s and t have length n > 1, and let a and b be the first characters, resp., of s and t.
Since s and t are LA, there is some bijective mapping φ between the characters of s and the characters of t such that x and φ(x) are LA for all x in s, meaning that |x - φ(x)| ≤ 1 for all x in s.
Let c = φ(a) and d = φ-1(b). Because of a's and b's minimality, a ≤ d (1) and b ≤ c (2).
Furthermore, since b and d, and a and c, and LA, d ≤ b + 1 (3) and c ≤ a + 1 (4).
By combining (1) and (3), and (2) and (4), we get that a ≤ d ≤ b + 1 and b ≤ c ≤ a + 1, from which we deduce that a - 1 ≤ b ≤ a + 1 and, therefore, that a and b are LA.
Now, by combining (1) and (4), and (2) and (3), we get that c - 1 ≤ a ≤ d and d - 1 ≤ b ≤ c, from which we deduce that c - 1 ≤ d ≤ c + 1 and, therefore that c and d are LA.
Thus, if we redefine φ by φ(a) = b and φ(d) = c, |x - φ(x)| ≤ 1 will still hold for all x in s and, in particular, for all x in s[1:].
This way, s[0] = a and t[0] = b, and s[1:] and t[1:], are LA.
Since s[1:] has length n - 1, this proves the necessity by induction.
