Lezione 16 (9 maggio 2000 h. 11-13)

Grado di un vertice

Definizione 16.1   Sia G un grafo e sia $v\in V(G)$, chiameremo grado di v il numero (cardinale) $\deg(v)=\left\vert\{e\in E(G) \mid v\in e\}\right\vert$. Diremo che v ha grado finito se $\deg(v)\in \mathbb N$.

Proposizione 16.2   Se G=(V,E) è un grafo finito, allora

$$\sum_{v\in V} \deg(v) = 2 \left\vert E\right\vert$$ (1)

Il lemma delle strette di mano

Proposizione 16.3   Se f è un isomorfismo tra G e G' e $v\in V(G)$ allora $\deg(v)=\deg(f(v))$.

Score di un grafo

Definizione 16.4   Sia G un grafo finito e sia $V(G)=\{v_1,\dots,v_n\}$, si chiama score di G la successione (finita)n-pla dei gradi dei suoi vertici ovvero $\mathop{\rm score}\nolimits(G)=(\deg(v_1),\dots,\deg(v_n))$.

Per scrivere lo score abbiamo dovuto ordinare i vertici del grafo e, ordinamenti diversi producono n-ple diverse, ma che coincidono a meno di riordinamento. Due score si considereranno quindi uguali se lo sono a meno di riordinarli. Per comodità si ordineranno i vertici in modo che la successione dei gradi sia non decrescente (i.e. $\deg(v_i)\le\deg(v_{i+1})$ per ogni i).

Teorema 16.5   Se G e G' sono grafi isomorfi, allora $\mathop{\rm score}\nolimits(G)=\mathop{\rm score}\nolimits(G')$.

Osservazione 16.6   Non è vero il viceversa del precedente teorema.

Teorema dello score