Determiniamo .
, quindi
. Ma allora la
soluzione è data da
.
Soluzione dell'esercizio 2 (1). Per induzione. Per è ovvio dalla definizione. Sia
e
supponiamo che la tesi sia vera per ogni
, allora
è somma di un numero pari (
) e di un numero,
, che, per
ipotesi di induzione, è dispari. Quindi
è dispari.
(2). Per induzione. Se ,
. Supponiamo la
tesi vera per
e proviamola per
. Dalla relazione di ricorrenza si ha
che
e per ipotesi di
induzione, quest'ultimo è
.
(3). Il polinomio caratteristico di tale equazione ricorsiva è
dato da le cui radici sono:
e
. Quindi una
generica soluzione della relazione ricorsiva è data da:
. Determiniamo
e
in modo che siano verificate le condizioni iniziali.
Soluzione dell'esercizio 3 Indichiamo con
. Per ogni
consideriamo l'applicazione
definita da
è una permutazione. Basta provare che è iniettiva
(dato che l'insieme di definizione è finito e coincide con il
codominio). Siano
: se
allora
, dato
che
è una permutazione; se
allora
, dato
che
è una permutazione; infine se
e
allora
e
e
poiché
.
Osserviamo ora che, per definizione,
, ossia abbiamo
definito una applicazione
. Proviamo che tale
applicazione è bigettiva.
è iniettiva. Se
esiste
tale che
e quindi
e
quindi
.
Analogamente se
allora
.
è surgettiva. Sia
, allora
, e dato che
è bigettiva, anche
e quindi
. È immediato allora vedere che
.
Ma allora
Soluzione dell'esercizio 4 Sia un vertice di grado
(massimo possibile), allora
è un grafo
connesso, quindi contiene un albero generatore
(ossia tale che
. Ma allora, per la relazione che lega il numero di vertici e il
numero di lati di un albero,
Il viceversa non è vero. Si consideri ad esempio il grafo rappresentato in
figura :
Soluzione dell'esercizio 5 Usiamo il teorema dello score:
![]() |
Soluzione dell'esercizio 6 Il primo grafo è hamiltoniano (in particolare quindi è -connesso) in
quanto c'è il ciclo
.
Il terzo grafo non è -connesso, infatti se a questo grafo si toglie il
vertice
si ottengono i due cicli
e
.
Il secondo e il terzo grafo sono isomorfi(quindi il primo e il secondo non lo
sono). Un isomorfismo è dato ad esempio dalla funzione definita da: