Question: What is the longest possible path in a grid graph? Prove it.
I know that there is a formula that says: the maximum length of a path in a graph with n vertices is n-1. I thought to prove it using the pigeon hole principle. But I'm not sure this is the right approach.
Thanks