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

Let Bn be the binary de Bruijn digraph of order n andW the quotient set of the set of vertices of Bn 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 Bn. 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.