Le graphe d'une grille

def graphe_grille(p: int, q: int) -> dict:
    G = {}
    for i in range(p):
        for j in range(q):
            voisins = []
            for (di, dj) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                ni, nj = i + di, j + dj
                if 0 <= ni < p and 0 <= nj < q:  # bornes limites
                    voisins.append((ni, nj))
            G[(i, j)] = voisins
    return G

Pour $2\times 3$, le graphe a 6 sommets et 7 arêtes ($\sum d(s)=14$).