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$$ (9)

Dimostrazione.  Siano $v_1,\dots,v_n$ i vertici di $G$ e $e_1,\dots,e_k$ i suoi lati. Per ogni $i=1,\dots,n$ e $j=1,\dots,k$ consideriamo il numero

$$m_{i,j}= \Big\langle \begin{array}{lcl} 1 &\hbox{\rm {se}} &v_i\in e_j\\ 0 &\hbox{\rm {se}} &v_i\not\in e_j \end{array}$$

Dalle proprietà associativa e commutativa della somma si ha evidentemente che

$$\sum_{i=1}^{n}\big(\sum_{j=1}^{k}m_{i,j}\big) = \sum_{j=1}^{k}\big(\sum_{i=1}^{n}m_{i,j}\big)$$ (10)

Ma fissato $i$ il numero $\sum_{j=1}^{k}m_{i,j}$ è uguale alla cardinalità dell'insieme $\{j\mid m_{i,j}=1\}=\{j\mid v_i\in e_j\}$ che è uguale al numero dei lati che contengono $v_i$, ossia $\sum_{j=1}^{k}m_{i,j}=\deg(v_i)$. Pertanto il lato sinistro dell'uguaglianza (10) è pari a $\sum_{i=1}^n\deg(v_i)$, ossia la somma dei gradi di tutti i vertici.

Invece, fissato $j$, il numero $\sum_{i=1}^{n}m_{i,j}$ è pari alla cardinalità dell'insieme $\{i\mid v_i\in e_j\}$, che è uguale a $2$, dato che ogni lato contiene esattamente due vertici. Ne consegue che il lato destro della (10) è uguale a $2k=2\left\vert E\right\vert$.     $\square$

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