Lemma forzatura alla connessione

[maluz1]

Buonasera,
Sul mio libro è presentato un certo lemma chiamato forzatura alla connessione, qui l'enunciato:

Lemma (“forzatura” alla connessione): Sia $ G = (V, E) $ un grafo finito e sia $ n = |V| $ il numero di vertici di G. Siano
$ d := min { deg(v) | v in V } $
$ D := max { deg(v) | v in V } $

Se $ d ≥ n − D − 1 $
allora G è connesso.

Tuttavia la dimostrazione non c'è. Per favore sapete spiegarmi almeno come si arriva a dirlo?
Anche perchè ho letto che è condizione sufficiente per affermare la connessione di un grafo.

[Trilogy]

Forse è l'ora, non ne sono sicuro al 100% ma ti dico come la farei io. A me sembra più intuitivo dimostrare che se $G$ non è connesso, allora vale $n-1>d+D$.

Puoi fare così: dimostralo per induzione su $n$. L'induzione puoi farla partire dal grafo non connesso che ti piace di più. Se ti sembra di imbrogliare usando i grafi con un vertice o zero vertici, puoi partire dal grafo non connesso con due vertici. Ad ogni modo dipende dalla definizione di grafo non connesso che tu hai.

Nel passo induttivo, considera un grafo $G$ non connesso con $n>2$ vertici. Puoi vederlo come un grafo non connesso $G'$ con $n-1$ vertici a cui hai aggiunto un nuovo vertice $v$ ed eventualmente un po' di edges qua e là che connettano $v$ ai vertici di $G'$. A questo punto, supponi per induzione che per $G'$ valga la tesi, cioè $n-2>d'+D'$, e dimostri che allora vale per $G$. Devi farti queste domande: quando aggiungiamo $v$ al grafo $G'$ e mettiamo eventualmente un po' di edges, cosa sono $d$ e $D$? Sono uguali a $d'$ e $D'$? Possono aumentare, diminuire,...? Vedi cosa può succedere, senza avere paura di considerare vari casi. Nei vari casi, vedi un po' se riesci a dimostrare che la tesi vale per $G$.