Para a questão, defina \( G_{n \times n} \) como um grafo não dirigido 2D grid com 4-vizinhança da seguinte forma:

cada vértice é identificado com uma coordenada inteira 2D, de (1,1) até (n,n); há n x n vértices, correspondendo a todos os valores de (1,1) até (n,n); em cada vértice incidem até 4 arestas, a saber, para um vértice (i,j)

(i,j) ↔ (i-1,j)

(i,j) ↔ (i+1,j)

(i,j) ↔ (i ,j-1)

(i,j) ↔ (i ,j+1)

onde as arestas não existem se alguma coordenada é < 1 ou > n. A Figura 1 (a seguir) mostra um exemplo para n = 5

Ao aplicar o algoritmo DFS a \( G_{n \times n} \) para obter uma árvore de busca, contendo apenas as arestas entre sucessor e antecessor na busca DFS, podemos afirmar sobre esta árvore: