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

Defina uma operação de 'contração' da seguinte forma:

para cada vértice u de grau 2

se u foi deletado, ignore e continue o 'para'.

v1 e v2 são os 2 vizinhos de u

se não existe aresta (v1,v2)

adicione ao grafo uma aresta (v1,v2)

delete u, (u,v1), (u,v2)

Se aplicarmos a operação de contração a \( G_{nxn} \), gerando um grafo \( G'_{nxn} \), quantos vértices e arestas a menos terá \( G'_{nxn} \) em relação ao grafo original, supondo n maior que 10: