Number of lines to connect $n \times n$ dots
I have found a paper that rigorously proves that $k_n = 2\cdot(n-1)$ using graph theory. It is however too long to summarize here. It also handles the cases of an $n \times m$ grid and other options with regard to the rules of the riddle.