Knight moves on 6x6 torus board define a 36-vertex bipartite (18 dark, 18 light squares) graph with all valencies=8. Note antipodal squares always have the opposite square-color.
Ugh --- grotesquely aliased lines --- see instead https://www.dropbox.com/s/8b0stotr8343mq2/semi_6x6.pdf The external edges obviously form a tour (closed Hamiltonian path); the remaining diagonals also form a tour, isomorphic to the first. Fred Lunnon [15/04/14]
--so if I understand aright, you took the 6x6 torus chessboard, and identified antipodal squares, thus getting 18 = (6*6/2) vertices, then used knight moves to define edges? Thus getting a graph of valency 4? Wrong. This would yield valency 8. So I do not understand what you did to create your graph.