Capire se dallo score posso trovare grafi sia connessi che sconnessi

BoG3
Ciao a tutti,
ho una domanda: dato uno score $d$ viene chiesto se è lo score di un grafo.

spesso nell'esercizio chiede:
Trova un grafo (se esiste) dello score $d$
1) esiste un grafo connesso?
2) esiste un grafo sconnesso?

So che ci sono 2 lemmi: forzatura alla connessione e forzatura alla sconnessione.

So che se è forzato alla connessione non ci sono grafi sconnessi dello score $d$ e se è forzato alla sconnessione non ci sono grafi connessi dello score $d$.

Ma in alcuni casi possono esistere grafi sia connessi che sconnessi appartenenti allo stesso score $d$.

Come posso capirlo?

GRazie mille

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.