Soluzioni proposte

Soluzione dell'esercizio 1 $(35,2)=1$ quindi $2$ è invertibile $\quad{\rm mod}\ 35$. Inoltre $\Phi(35)=24$ e $(7,24)=1$, quindi la congruenza è risolubile. Un inverso di $7$ $\quad{\rm mod}\ 24$ è dato da $7$ e quindi le soluzioni della congruenza sono date da $\left[2^7\right]_{35}=\left[23\right]_{35}$.

Il sistema è quindi equivalente a

$$\begin{cases} x \cong 23 & \quad{\rm mod}\ 35 \\ x \cong 16 & \quad{\rm mod}\ 55 \end{cases}$$

che non ha soluzione dato che $(35,55)=5 \not\mathrel{\big\vert}7 = 23 -16$.     

Soluzione dell'esercizio 2 Diamo solo i risultati, per la prova si veda la soluzione dell'analogo esercizio nell'altro compito di questo appello. $\left\vert A\right\vert=15$ e $\left\vert B\right\vert=\Phi(15)=8$.

(1). $\left\vert\mathcal{X}_1\right\vert= \left\vert{B \choose 6} \times 2^{A\setminus B}\right\vert = {8 \choose 6}2^{7}=28\cdot 128 = 3584$.

(2). $\left\vert \mathcal{X}_2\right\vert = \left\vert S_B \times A^{A\setminus B}\right\vert = 8!\cdot 15^{7}$.

(3). $\left\vert \mathcal{X}_3\right\vert = \left\vert S_B \times S_{A\setminus B}\right\vert = 8!\cdot 7!$.     

Soluzione dell'esercizio 3 In $d_2$ ci sono un numero dispari di numeri dispari, quindi non può essere lo score di un grafo.

Per $d_2$ usiamo il teorema dello score:

$$\begin{array}{lcl} d_2 & = & (1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 3, 3,... ... 1, 1, 2, 2, 2, 2)\\ d_2'' & = & (1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1) \end{array}$$

Dato che $d_2''$ è realizzabile come score di un grafo, anche $d_2$ lo è. La costruzione standard produce il grafo in figura che è sconnesso.

Figura 1: Il grafo costruito per la soluzione dell'esercizio 3. La configurazione di partenza è data dai vertici e lati neri a cui si aggiungono nell'ordine quelli rossi e quelli blu.

(1). La risposta è sì. Ad esemoio quello in figura.

Figura 2: Un albero che realizza lo score $d_1$ dell'esercizio 3.

(2). La risposta è sì. Ad esempio quello in figura.

(3). La risposta è no. Un grafo hamiltoniano ha tutti i vertici di grado almeno $2$.     

Soluzione dell'esercizio 4 Sia $T=(V,E)$ un tale albero e sia $V=\{v_1, v_2,\dots,v_{13}\}$ con $\deg(v_i)=1$ per $i=1,2.\dots,10$. Allora dato che $T$ è un albero $\left\vert E\right\vert =\left\vert V\right\vert-1=12$ e quindi

$$24 = 2 \left\vert E\right\vert = \sum _{i=1}^{13} \deg(v_i) = 10 + \deg(v_{11}) + \deg (v_{12}) + \deg (v_{13}).$$

Se non ci fossero vertici di grado $5$ allora si avrebbe che $\deg (v_j) \le 4$ per ogni $j$ e dalla relazione precedente si otterrebbe:

$$24 \le 10 + 4 + 4 + 4 = 22$$

che è un assurdo.