Le degré des sommets

Le code.

G = {0: [1], 1: [0, 2, 3], 2: [1, 3], 3: [1, 2]}

def degres(G):
    return {s: len(G[s]) for s in G}

def nb_aretes(G):
    total = 0
    for s in G:
        total = total + len(G[s])
    return total // 2          # chaque arete a ete comptee deux fois

d = degres(G)
print(d)                                   # {0: 1, 1: 3, 2: 2, 3: 2}
print(sum(d[s] for s in d), 2 * nb_aretes(G))   # 8 8

Vérification à la main. Les arêtes sont $\{0,1\}$, $\{1,2\}$, $\{1,3\}$ et $\{2,3\}$ : il y en a $4$. Les degrés sont $1,3,2,2$, de somme $8=2\times 4$. ✔

Pourquoi la somme des degrés vaut le double du nombre d'arêtes. Le degré d'un sommet est le nombre d'arêtes qui l'atteignent. En sommant les degrés sur tous les sommets, chaque arête $\{u,v\}$ est comptée deux fois : une fois dans le degré de $u$, une fois dans celui de $v$. D'où

$$\sum _s\mathrm{deg}(s)=2\times (\text{nombre d’areˆtes}).$$

C'est ce qui justifie le // 2 de nb_aretes.

Une conséquence immédiate. La somme des degrés est toujours paire. Un graphe dont les degrés seraient $1,1,1$ ne peut donc pas exister — leur somme vaut $3$. C'est un contrôle de cohérence gratuit sur toute donnée de graphe.

Le contrôle de symétrie. Dans un graphe non orienté, la structure doit vérifier : $v$ figure dans G[u] si et seulement si $u$ figure dans G[v]. Une saisie asymétrique fausserait les degrés sans provoquer d'erreur. On peut le vérifier ainsi :

def symetrique(G):
    for u in G:
        for v in G[u]:
            if u not in G[v]:
                return False
    return True