Lezione 17 (14 maggio 2001 h. 9.30-10.30)

Grado di un vertice

Definizione 17.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 17.2   Se G=(V,E) è un grafo finito, allora

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

Il lemma delle strette di mano

Proposizione 17.3   In un grafo il numero di vertici di grado dispari è pari.

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

Score di un grafo

Definizione 17.5   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 17.6   Se G e G' sono grafi isomorfi, allora $\mathop{\rm score}\nolimits(G)=\mathop{\rm score}\nolimits(G')$.

Osservazione 17.7   Non è vero il viceversa del precedente teorema, si vedano ad esempio i grafi i due grafi di figura 5 dell'esercizio 14.11.

Teorema dello score