Choose a positive integer d. Now consider the graph whose vertices are the ordered pairs (x,y) of integers, and two vertices are connected if and only if the square of the euclidean distance between them is d. For what values of d does this graph have an odd cycle?
None. There must be a smallest value of d such that the graph has an odd cycle, call it d'. Now color all the vertices of the graph either black or white in a checkerboard pattern. In other words color a vertex white if the sum of the coordinates is even and color it black if the sum of the coordinates is odd. Now if d is odd each edge connects a white vertex to a black vertex, and so any cycle must be even. So d' must even, and therefore all the vertices are the same color. If all the points are white then if we map each point (x,y) to ((x+y)/2,(x-y)/2) then each vertex of our path maps to an integer lattice point, and the square of the distances between the transformed points is d'/2, therefore d' cannot be the smallest distance. If the vertices are black then mapping (x,y) to ((x+y+1)/2,(x-y+1)/2) shows that there exists a cycle with shorter edges. Therefore no smallest length fo an odd cycle exists, and so no odd cycle exists.
