![]() |
![]() |
![]() |
|
![]() |
![]() |
![]() |
|
![]() |
![]() |
![]() |
|
![]() |
![]() |
![]() |
Soluzione dell'esercizio 2 (1).
L'insieme
è in bigezione con
, una bigezione essendo
data da
definita ponendo
. Ma allora
(2).
è in bigezione con
, una
bigezione è data da
definita ponendo
. Ma allora
(3).
, infatti
equivale a
dire che
. Ma allora
Soluzione dell'esercizio 3 Un grafo tale che
dovrebbe avere
vertici di grado
dispiri, ma sappiamo che in ogni grafo il numero di vertici di grado dispari è
pari, quindi un tale
non può esistere.
Per usiamo il teorema dello score:
![]() |
(1). La risposta è si. Con un po' di attenzione si può costruire il grafo di figura, che è un albero.
(2). La risposta è sì. Il grafo costruito in figura è evidentemente sconnesso.
(3).
Un tale grafo non potrà certamente essere -connesso dato che contiene
necessariamente dei vertici di grado
, e sappiamo che ciò è impossibile
nei grafi
-connessi.
Soluzione dell'esercizio 4 non è
-connesso, infatti se glio si toglie il
vertice
si ottengono i due cicli disgiunti
e
.
Il grafo è hamiltoniano (e quindi quindi è
-connesso) in
quanto c'è il ciclo
che contiene tutti i vertici.
Anche il grafo è hamiltoniano (e quindi quindi è
-connesso) in
quanto c'è il ciclo
.
Di conseguenza il primo ed il secondo grafo non sono isomorfi
e
.
Neanche e
sono isomorfi, infatti in
c'è un vertice
che ha grado
ed i vertici a lui adiacenti
e
hanno entrambi
grado
. Se ci fosse un isomorfismo
dovrebbe esserci un vertice
in
con le stesse proprietà, ma i quattro vertici di
che
hanno grado
sono adiacenti ciascuno ad al più un vertice di grado
,
più esplicitamente: