Calculer le degré de chaque sommet

def degres(G):
    return {u: len(voisins) for u, voisins in G.items()}

G = {0: [1, 2], 1: [0, 2], 2: [0, 1, 3], 3: [2]}
d = degres(G)
print(d)                       # {0: 2, 1: 2, 2: 3, 3: 1}
print(sum(d.values()))         # 8
print(2 * 4)                   # 8 : il y a bien 4 aretes

La somme des degrés vaut $8=2\times 4$, conforme au lemme des poignées de main. La complexité est $O(n)$ car on parcourt chaque sommet une fois.