the graph with nodes labeled where each node i is adjacent to 2k nodes . The graph is connected if and only if . If are fixed integers then the number of spanning trees where satisfies a recurrence relation of order . In particular, where is the n-th Fibonacci number. Self-complementary circulants A self-complementary graph is a graph in which replacing every edge by a non-edge and vice versa produces an isomorphic graph. For instance, a five-vertex cycle graph is self-complementary, and is also a circulant graph. More generally every Paley graph of prime order is a self-complementary circulant graph. Horst Sachs showed that, if a number has the property that every prime factor of is congruent to , then there exists a self-complementary circulant with vertices. He conjectured that this condition is also necessary: that no other values of allow a self-complementary circulant to exist. The conjecture was proven some 40 years later, by Vilfred. Ádám's conjecture Define a circulant numbering of a circulant graph to be a labeling of the vertices of the graph by the numbers from 0 to in such a way that, if some two vertices numbered and are adjacent, then every two vertices numbered and are adjacent. Equivalently, a circulant numbering is a numbering of the vertices for which the adjacency matrix of the graph is a circulant matrix. Let be an integer that is relatively prime to , and let be any integer. Then the linear function that takes a number to transforms a circulant numbering to another circulant numbering. András Ádám conjectured that these linear maps are the only ways of renumbering a circulant graph while preserving the circulant property: that is, if and are isomorphic circulant graphs, with different numberings, then there is a linear map that transforms the numbering for into the numbering for . However, Ádám's conjecture is now known to be false. A counterexample is given by graphs and with 16 vertices each; a vertex in is connected to the six neighbors , , and modulo 16, while in the six neighbors are , , and modulo 16. These two graphs are isomorphic, but their isomorphism cannot be realized by a linear map. Toida's conjecture refines Ádám's conjecture by considering only a special class of circulant graphs, in which all of the differences between adjacent graph vertices are relatively prime to the number of vertices. According to this