Soluzione dell'esercizio 2 (1).
,
. Ma allora
e quindi
. Invece
.
(2). Indichiamo con l'insieme delle permutazioni di
e con
l'insieme delle permutazioni di
. Allora la funzione
![]() |
![]() |
![]() |
|
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
|
![]() |
![]() |
![]() |
(3).
Affinché una funzione
non sia suriettiva è
necessario e sufficiente che sia non costante. D'altra parte le
funzioni
non costanti sono esattamente
e quindi
.
Soluzione dell'esercizio 3 (1).
Sia il numero di vertici di grado
e
il numero di vertici
di grado
. Dato che ci sono soltanto vertici di grado
,
e
, e quelli di grado
sono
, si ha che
. Ma allora, dato che
è un albero
(2). I due alberi in figura 1 hanno la
proprietà richiesta (esattamente 5 vertici di grado ) ma non sono
isomorfi, dato che hanno un numero diverso di vertici
(3). Se è un albero con la proprietà suddetta, e
è una sua foglia, allora se
si consideri
l'albero
. Chiaramente
ha ancora la stessa proprietà, ma ha un vertice in
più. Con questa tecnica si possono allora costruire una
infinità di alberi a dua a due non isomorfi, in quanto aventi un
diverso numero di vertici, ma tutti con esattamente
vertici di
grado
.
Soluzione dell'esercizio 4 (1).
Si verifica immediatamente che
Allo stesso modo
Pertanto i due grafi essendo uno connesso e ed uno sconnesso non sono isonmrfi.
(2).
Prendendo si ha che