Soluzioni proposte

Soluzione dell'esercizio 1 $29$ è primo, quindi $3$ è invertibile $\quad{\rm mod}\ 29$. Inoltre $\Phi(29)=28$ e $(17,28)=1$, quindi la congruenza è risolubile. Un inverso di $17$ $\quad{\rm mod}\ 28$ è dato da $5$ e quindi le soluzioni della congruenza sono date da $\left[3^5\right]_{29}=\left[11\right]_{29}$.     

Soluzione dell'esercizio 2 (1). $10=\left\vert{A \choose 3}\right\vert = {\left\vert A\right\vert \choose 3}={n \choose 3} = n(n-1)(n-2)/6$ se e solo se $n(n-1)(n-2)=60$. Dato che gli unici tre numeri consecutivi il cui prodotto fa $60$ sno $3$, $4$ e $5$, si ha che $n=5$.

Per le altre risposte si veda la soluzione dell'altro compito di questo appello.     

Soluzione dell'esercizio 3 Se $G=(V,E)$ è un grafo tale che $\mathop{\rm score}\nolimits (G)=d_2$ allora $\left\vert V\right\vert=9$ e ci sono due vertci di grado $7$, chiamiamoli $u$ e $v$. Ma allora i vertci che sono adiacenti sia a $u$ che a $v$ devono essere almeno $5$ (in un insieme con $9$ elementi due sottinsiemi dicardinalità $7$ hanno intersezione di cardinalità almeno $7+7-9=5$) e quindi ci dovrebbero essere almeno $5$ vertici diversi da $u$ e $v$ con grado almeno $2$. Ciò è in contraddizione con il fatto che di vertici di grado $\ge 2$ e diversi da $u$ e $v$ ce ne dovrebbero essere soltanto $3$.

Per $d_1$ usiamo il teorema dello score:

$$\begin{array}{lcl} d_1 & = & (2, 2, 3, 3, 4, 4, 7, 7) \\ d_1' & = & (1, 1, 2, 2, 3, 3, 6) \\ d_1'' & = & (0, 0, 1, 1, 2, 2) \end{array}$$

Dato che $d_1''$ è realizzabile come score di un grafo, anche $d_1$ lo è. La costruzione standard produce il grafo in figura che è $2$-connesso.

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 prima quelli rossi e quindi quelli blu.

(1). La risposta è no. Ogni albero finito havertici di grado $1$, mentre in un tale grafo ogni vertice ha grado $\ge 2$.

(2). La risposta è no. Se $G=(V,E)$ è un grafo tale che $\mathop{\rm score}\nolimits (G)=d_1$ allora esiste $v\in V$ tale che $\deg(V)=7$, ossia ogni altro vertice gli è adiacente. Quindi $G$ è connesso.

(3). Che il grafo di figura 1 sia $2$-connesso lo si può vedere ad esempio mostrando che è ottenuto da un ciclo con successive aggiunzioni e suddivisioni di lati.     

Soluzione dell'esercizio 4 Il primo ed il terzo grafo sono tra loro isomorfi e contengono evidentemente dei $3$-cicli. Il secondo non contiene $3$-cicli (per una motivazione si veda la soluzione dell'altro compito di questo appello) e quindi non è isomorfo agli altri due.