Il sistema è equivalente a
Soluzione dell'esercizio 2 Sia . Un grafo
ammette come albero di copertura
se e solo
se ha come insieme di vertici
(i.e.
) e se ha
come
sottografo ossia se e solo se
. Ma allora l'insieme
dei grafi richiesto è in bigezione con l'insieme
Dato che
allora
e quindi la
cardinalità cercata è pari a
Soluzione dell'esercizio 3 Se è un grafo tale che
allora
e ci sono due vertci di grado
. Ma allora ogni altro vertice deve
essere adiacente a questi due, e quindi ogni altro vertice dovrebbe
avere grado almeno
, mentre in
c'è un
.
Per usiamo il teorema dello score:
(1).
La risposta è no. Ogni albero finito ha vertici 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 gli
è adiacente. Quindi ogni vertice è congiungibile a
e quindi
è connesso.
(3). La risposta è sì. Il grafo costruito
sopra, attaccando un vertice
ad ogni vertice di
non è
-connesso, dato che
è sconnesso.
Soluzione dell'esercizio 4
è l'insieme degli elementi invertibili di
e
quindi
.
(1). Osserviamo che ,
,
, quindi
i lati di
sono dati da
![]() |
![]() |
![]() |
|
![]() |
![]() |
Invece
e quindi i lati sono dati da
![]() |
![]() |
![]() |
(2). Per quanto osservato sopra, basta trovare tutti gli
tali che
e
. Si vede facilmente che questo
insieme è
.
(3).
Un tale esiste, basta prendere
. In questo caso infatti il
grafo non ha lati e quindi non è isomorfo né a
né a
.