3
$\begingroup$

Consider an $n\times n$ grid graph. It is easy to construct (self-avoiding) paths in it of length $n(n+2)$, by starting at the upper left corner, going downwards to the lower left corner, going right by 1 edge, going upwards, going right by 1 edge etc (zig zagging). How does one rigorously show that this is indeed the maximum possible length of a path in the grid? Furthermore, is there a formula counting the number of said paths?

$\endgroup$
2
$\begingroup$

There cannot be any longer paths, since each intersection can only be used once, and there are $(n+1)^2 = n(n+2) + 1$ intersections. Any path of $i$ nodes is of length $i-1$. The only exception is if (hamiltonian) loops counts as self-avoiding, and exists.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.