Capire se dallo score posso trovare grafi sia connessi che sconnessi
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
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