Strutture geometriche e algebriche - dimostrazione della condizione necessaria per un grafo G connesso

Dimostrazione della condizione necessaria per un grafo connesso

Introduzione

Dimostriamo che per un grafo G connesso: \( E(G) \geq V(G) - 1 \). Si utilizza l’induzione!

Caso base

Dimostriamo che è vero nel caso \( n = 2 \). Evidentemente è vero perché avremo soltanto 2 nodi e un lato (di sicuro perché è connesso), come nella figura seguente: \( E(G) = 1 \), \( V(G) - 1 = 2 - 1 = 1 \), quindi è vera.

Infatti, in tal caso, \( E(G) = 1 \) e \( n - 1 = 1 \).

Ipotesi induttiva

Adesso, prima di procedere con l’ipotesi induttiva, supponiamo di prendere un vertice \( v \in V(G) \) la cui valenza sia \( d(v) = k \) (dove \( 1 \leq k \leq n - 1 \) visto che G è connesso e quindi il vertice al limite sarà collegato ad uno solo degli altri vertici oppure a tutti gli altri). Stacchiamo questo vertice dal grafo G.

Analisi del grafo ridotto

Così facendo otteniamo un certo numero \( l \) di componenti connesse \( G_1, G_2, ..., G_l \).

Precisamente, otterremo una sola componente connessa (\( l = 1 \)) quando tutti gli altri vertici distinti da \( v \) erano comunque collegati tra loro, come in figura:

[Con il tratteggio indico gli spigoli che vengono eliminati eliminando il vertice \( v \)]

Invece, avremo \( k \) componenti connesse nel caso in cui \( v \) era collegato ad altri nodi (a loro volta eventualmente collegati ad altri ma non tra di loro) e li teneva uniti tipo il centro di una stella, come nella seguente figura: \( v \ldots \)

Conclusione

Per ipotesi induttiva possiamo affermare che: \( E(G_i) \geq V(G_i) - 1 \) per ogni componente \( G_i \) del grafo ridotto.