A graph-theoretic proof of the non-existence of self-orthogonal Latin squares of order 6 (Q539882)

This paper shows without resort to an exhaustive search by computer or human that a latin square of order 6 cannot be orthogonal to its transpose. If a latin square of order \(n\) is orthogonal to its transpose, then, if \(L(i,j)\) denotes the entry at cell \((i,j)\), the ordered pairs \((L(i,j),L(j,i))\) sweep out the \(n^2\) ordered pairs \((a,b)\), \(1 \leq a,b \leq n\). The main tool is a directed graph whose vertices are the \(n(n-1)/2\) unordered pairs \((i,j)\), \(i \neq j\). It is shown that this graph, if it exists, has no cycle of length less than 5 but has cycles of length 5, and then that this graph cannot exist. It is suggested that the technique may be of use in investigating orthogonal latin squares.