Proving that a latin square has a set amount of edges.

Question

I was reading this article that states (page 3)that the total number of edges of a latin square when converting it to a graph is $$ n^2 (n-1) $$

Can someone please prove why this is true?

Here's the link: http://www.cs.cornell.edu/gomes/gs-csgc.pdf

thanks

Answer 1

A Latin square has a graph representation, in which cells in the Latin square correspond to the nodes of the graph, and whenever two cells are in the same row or column, there is an edge between the corresponding nodes in the graph.

Let $P$ be a Latin square of order $n$. Then the graph of $P$ has $n^2$ nodes, since $P$ has $n^2$ cells.

Let's count the number of edges. If $c$ is some cell of $P$, then $c$ is in the same row as $n-1$ other cells, and in the same column as $n-1$ other cells. Thus there are $2(n-1)$ edges connected to the node corresponding to $c$. Since there is a total of $n^2$ cells, this gives $2(n-1)n^2$ edges, and as each edge has been counted twice, we end up with the required $(n-1)n^2$.