Abstract
An n-bit Gray code is a sequence of all n-bit strings such that consecutive strings differ in a single bit. It is well-known that given such strings α, β, an n-bit Gray code between α and β exists iff the Hamming distance d(α,β) of α and β is odd.
We generalize this classical result to k pairwise disjoint pairs of n-bit strings αi,βi : if d(αi,βi) is odd for all i and k 1 with one exception in the case that n = k + 1 = 4. Our result is optimal in the sense that for every n > 2 there are n pairwise disjoint pairs of n-bit strings αi,βi with d(αi , βi ) odd for which such sequences do not exist.