Soluzioni proposte

Soluzione dell'esercizio 1 $(2,55)=1$ quindi $2$ è invertibile $\quad{\rm mod}\ 55$. $\Phi(55)=40$ e $(40,33)=1$, quindi $33$ è invertibile $\quad{\rm mod}\ \Phi (55)$ e il suo inverso è dato da $17$. La soluzione della congruenza è datat allora da $\left[2^{17}\right]_{55}=\left[7\right]_{55}$.

Il sistema è equivalente a

$$\begin{cases} x \equiv 7 \quad{\rm mod}\ 55 \\ x \equiv 3 \quad{\rm mod}\ 115 \end{cases}$$

che non è risolubile, dato che $(55,115)=5 \not\mathrel{\mathrel{\Big\vert}}4 = 7-3$.     

Soluzione dell'esercizio 2 Sia $T$. Un grafo $G$ ammette come albero di copertura $T$ se e solo se ha come insieme di vertici $V(T)$ (i.e. $V(G)=V(T)$) e se ha $T$ come sottografo ossia se e solo se $E(G)\supseteq E(T)$. Ma allora l'insieme dei grafi richiesto è in bigezione con l'insieme

$$\bigg\{ E \subseteq {V(T) \choose 2} \bigg\vert E\supseteq E(T) \bigg\} = 2 ^ {{V(T) \choose 2}-E(T)}$$

Dato che $\left\vert V(T)\right\vert=n$ allora $\left\vert E(T)=n-1\right\vert$ e quindi la cardinalità cercata è pari a

$$\left\vert 2 ^ {{V(T) \choose 2}-E(T)}\right\vert = 2^{\left\vert... ... 2^{({n \choose 2}-n+1)} = 2^{\frac{n(n-1)}{2}-n+1} = 2^{\frac{(n-1)(n-2)}{2}}$$

    

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 $8$. Ma allora ogni altro vertice deve essere adiacente a questi due, e quindi ogni altro vertice dovrebbe avere grado almeno $2$, mentre in $d_2$ c'è un $1$.

Per $d_1$ usiamo il teorema dello score:

$$\begin{array}{lcl} d_1 = (3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 12) \\ d_1' = (2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3) \end{array}$$

$d_1'$ è realizzabile, ad esempio è lo score del grafo $C_8\amalg K_4$, unione disgiunta di una copia di $C_8$ con una copia di $K_4$, quindi anche $d_1$ è realizzabile (basta aggiungere un vertice $v$ e collegarlo con tutti i vertici di $C_8\amalg K_4$).

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

(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)=12$, ossia ogni altro vertice gli è adiacente. Quindi ogni vertice è congiungibile a $v$ e quindi $G$ è connesso.

(3). La risposta è sì. Il grafo $G$ costruito sopra, attaccando un vertice $v$ ad ogni vertice di $C_8\amalg K_4$ non è $2$-connesso, dato che $G-v = C_8\amalg K_4$ è sconnesso.     

Soluzione dell'esercizio 4  $(\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}15\mathbb{Z}}} {{}_{\!\text... ..._{\!\scriptstyle {}15\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}15\mathbb{Z}}})^*$ è l'insieme degli elementi invertibili di $\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}15\mathbb{Z}}} {{}_{\!\texts... ...{{}_{\!\scriptstyle {}15\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}15\mathbb{Z}}}$ e quindi $(\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}15\mathbb{Z}}} {{}_{\!\text... ...athbb{Z}}} {{}_{\!\scriptscriptstyle {}15\mathbb{Z}}})^*=\{1,2,4,7,8,11,13,14\}$.

(1). Osserviamo che $2^2=4$, $2^3=8$, $2^4=16=1$, quindi i lati di $H$ sono dati da

$$E(H) = \big\{ \{1,2\},\{2,4\},\{4,8\},\{8,1\}, \{7,7\cdot2\}, \{7\cdot2,7\cdot4\}, \{7\cdot4,7\cdot8\}, \{7\cdot8,7\cdot1\} \big\}$$

$$= \big\{ \{1,2\},\{2,4\},\{4,8\},\{8,1\}, \{7,14\}, \{14,13\}, \{13,11\}, \{11,7\} \big\}$$

e quindi $H$ è isomorfo all'unione disgiunta di due copie di $C_4$.

Invece $11^2=121=1$ e quindi i lati sono dati da

$$E(K) = \big\{ \{1,11\},\{2,7\},\{4,9\},\{8,13\} \big\}$$

e quindi $K$ è isomorfo all'unione disgiunta di $4$ copie di $P_2$.

(2). Per quanto osservato sopra, basta trovare tutti gli $n$ tali che $n^4=1$ e $n^3=\ne1$. Si vede facilmente che questo insieme è $\{2,8,7,13\}$.

(3). Un tale $n$ esiste, basta prendere $n=1$. In questo caso infatti il grafo non ha lati e quindi non è isomorfo né a $H$ né a $K$.