Question

An m × n grid graph has m rows of n vertices with vertices closest to each other connected by an edge. Find the greatest length of any path in such a graph, and provide a brief explanation as to why it is maximum. You can assume m, n ≥ 2. Please provide an explanation without using Hamilton Graph Theory.

Answer 1

A grid graph is exactly what it sounds like, especially since we are considering the case of a 2 dimensional one. It looks like this

where the difference lies in the number of rows and columns. There is an edge between two vertices if and only if one of them is directly (immediately) below or beside the other.

A path in a graph is a sequence of vertices in the graph such that for all , the vertices are adjacent, and , i.e., all elements of the sequence are distinct.

Now, an m × n grid graph has m rows of n vertices with vertices closest to each other connected by an edge. So, the graph has a total of mn vertices.

• Since all vertices in a path must be distinct, the path can have no more than mn vertices.
• Since the vertices are all distinct in a path, the edges must also be distinct.

Then, any path can have each of the graph's vertices atmost once. Let us see the paths below:

We can form a path like any one of the two paths above in the m×n grid graph for any . So, each grid graph has a path consisting of all mn vertices of the graph.

Now, the path is a series of mn vertices, say . Then, the edges in this path are , or . So, the path has (mn-1) edges.

So, the length of the greatest path in the m×n grid graph is

, which is a maximum because no longer path is possible (as all vertices of the graph are included) and all grid graphs DO have paths of this length.