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

Marque a resposta mais exata e precisa. O número de arestas em \( G_{n \times n} \) é: