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

Dimostrazione della condizione necessaria per un Grafo G connesso:

Dimostriamo che ⇒

= ≥ −

G grafo connesso con V (

G ) n E (

G ) n 1

Si usa l’induzione! = =

Dimostriamo che è vero nel caso , caso base (il caso è caso banale quindi passiamo a

n 2 n 1

= ).

n 2

Evidentemente è vero perché avremo soltanto 2 nodi e un lato (di sicuro perché è connesso) come

nella figura seguente: = ≥ − = − = quindi è vera.

Infatti in tal caso E (

G ) 1 n 1 2 1 1 ∈

v V (G ) la

Adesso prima di procedere con l’ipotesi induttiva supponiamo di prendere un vertice

= ≤ ≤ −

d ( v ) k

cui valenza sia (dove visto che G è connesso e quindi il vertice al limite sarà

1 k n 1

collegato ad uno solo degli altri vertici oppure a tutti gli altri ) e stacchiamolo dal grafo G. Così

n-1

di componenti connesse , ,..., . Si vede che risulta

facendo otteniamo un certo numero G G G

l 1 2 l

≤ ≤ =

. Precisamente otterremo una sola componente connessa ( ) quando tutti gli altri vertici

1 l k l 1

distinti da erano comunque collegati tra loro come in figura:

v

v

[Con il tratteggio indico gli spigoli che vengono eliminati eliminando il vertice ]

v

componenti connesse nel caso in cui era collegato ad altri nodi (a loro volta

Invece avremo k v k

eventualmente collegati ad altri ma non tra di loro) e li teneva uniti tipo il centro di una stella come

nella seguente figura: v …

= ≥ −

. Per ipotesi induttiva possiamo affermare che

Sia allora ( ) ( ) 1

n V G E G n

i i i i