Perfect matchings of a graph associated with a binary de Bruijn digraph

Let B n be the binary de Bruijn digraph of order n and W the quotient set of the set of vertices of B n with respect to the equivalence relation of rotation. Let G be the graph which has W as the set of vertices and in which two elements C and H are adjacent when there exist a vertex v of C and a vertex u of H such that ( v , u ) is an arc of B n . Recently the problem of establishing whether the graph G has a perfect matching was posed. In this paper we answer in the positive to this problem in the case of n odd.