L'insieme delle soluzioni è allora dato da
.
Soluzione dell'esercizio 2 (1).
.
(2). Sia
e
, allora l'insieme
è
evidentemente in bigezione con
e quindi
.
(3).
L'insieme
coincide con l'insieme
non è costante
. Quindi la sua cardinalità è
pari a
.
Soluzione dell'esercizio 3 Se è un grafo tale che
allora
e ci sono due vertci, chiamiamoli
e
, di grado rispettivamente
e
. Ma allora i
vertci che sono adiacenti sia a
che a
devono essere almeno
(in un insieme con
elementi due sottinsiemi dicardinalità
e
hanno intersezione di cardinalità almeno
) e quindi ci dovrebbero
essere almeno
vertici diversi da
e
con grado almeno
. Ciò è in contraddizione con il fatto che di vertici di grado
e diversi da
e
ce ne dovrebbero essere soltanto
.
Per usiamo il teorema dello score:
![]() |
(1).
La risposta è no. Ogni albero finito havertici di grado , mentre
in un tale grafo ogni vertice ha grado
..
(2).
La risposta è no. Se è un grafo tale che
allora
esiste
tale che
, ossia ogni altro vertice, tranne
uno, è adiacente e
quindi congiungibile con
. D'altra parte l'unico vertice non ancora
considerato ha grado positivo, e quindi deve essere congiungibile con
almeno uno degli altri. Quindi
è connesso.
(3).
Che il grafo di figura 1 sia -connesso lo si può
vedere ad esempio mostrando che è ottenuto da un ciclo con
successive aggiunzioni e suddivisioni di lati.
Soluzione dell'esercizio 4 non è
-connesso, infatti
è dato
dall'unione disgiunte di due
. Anche
non è 2-connesso,
dato che
è isomorfo all'unione disgiunta di due
.
Invece
è hamiltoniano (e quindi
-connesso) in quanto
contiene il ciclo
.
Di conseguenza
e
.
Anche
, dato che in
ogni vertice di grado
è adiacente ad un altro vertice di grado
, mentre in
i
vertici
e
hanno grado
ma sono adiacenti solo a vertici di
grado
.