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 è un grafo connesso con V(G) ≥ E(G) - 1.

Si usa l'induzione!

Dimostriamo che è vero nel caso base, caso banale (il caso è banale quindi passiamo a n = 2).

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

G = {V(G), E(G)} = {2, 1} quindi è vera.

Infatti in tal caso E(G) = 1 ≤ V(G) - 1 = 2 - 1 = 1 quindi è vera.

Adesso prima di procedere con l'ipotesi induttiva supponiamo di prendere un vertice v ∈ V(G) il cui grado sia d(v) ≤ k (dove k ≤ 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) e stacchiamolo dal grafo G. Così facendo otteniamo un certo numero n - 1 di componenti connesse, G1, G2, ..., Gl. Si vede che risulta:

V(G) = V(G1) ∪ V(G2) ∪ ... ∪ V(Gl) e E(G) = E(G1) ∪ E(G2) ∪ ... ∪ E(Gl).

Precisamente otterremo una