Graphes et matrice d'adjacence

a) Si un graphe d'ordre 5 avait tous ses sommets de degré 3, la somme des degrés serait $5 \times 3 = 15$, un nombre impair. Or cette somme vaut $2 \times (\text{nombre} d'\text{arêtes})$, donc elle est paire. Contradiction : un tel graphe n'existe pas.
b) Pour un graphe d'ordre 6 tout entier de degré 3, la somme des degrés est $6 \times 3 = 18$, nombre pair. Le nombre d'arêtes serait $18 \div 2 = 9$. Un tel graphe existe (par exemple le prisme triangulaire : deux triangles reliés par trois arêtes, chaque sommet ayant degré 3).
c) Notons $S_p$ la somme des degrés des sommets de degré pair et $S_i$ celle des sommets de degré impair. La somme totale des degrés est $S_p + S_i = 2 \times (\text{nombre} d'\text{arêtes})$, donc elle est paire.
$S_p$ est une somme de nombres pairs : elle est paire. Donc $S_i = (S_p + S_i) - S_p$ est paire (différence de deux nombres pairs).
Or $S_i$ est une somme de nombres impairs. Une somme d'entiers impairs est paire si et seulement si le nombre de termes est pair. Donc le nombre de sommets de degré impair est pair. C'est le lemme des poignées de main.

a) On utilise $M^{n+1} = M^{n} \times M$ et la matrice M du triangle ($M_{11}$ = 0, $M_{12}$ = $M_{13}$ = 1, etc.).
$u_{n+1} = (M^{n+1})_{11}$ = Σ $(M^{n})_{1k} M_k1 = (M^{n})_{11}\times 0 + (M^{n})_{12}\times 1 + (M^{n})_{13}\times 1 = v_{n} + v_{n} = 2 v_{n}$.
$v_{n+1} = (M^{n+1})_{12}$ = Σ $(M^{n})_{1k} M_k2 = (M^{n})_{11}\times 1 + (M^{n})_{12}\times 0 + (M^{n})_{13}\times 1 = u_{n} + v_{n}$.
b) On applique $u_{0} = 1$, $v_{0} = 0$ :
$n=1$ : $u_{1} = 2 v_{0} = 0$ ; $v_{1} = u_{0} + v_{0} = 1$.
$n=2$ : $u_{2} = 2 v_{1} = 2$ ; $v_{2} = u_{1} + v_{1} = 0 + 1 = 1$.
$n=3$ : $u_{3} = 2 v_{2} = 2$ ; $v_{3} = u_{2} + v_{2} = 2 + 1 = 3$.
$n=4$ : $u_{4} = 2 v_{3} = 6$ ; $v_{4} = u_{3} + v_{3} = 2 + 3 = 5$.
$n=5$ : $u_{5} = 2 v_{4} = 10$ ; $v_{5} = u_{4} + v_{4} = 6 + 5 = 11$.
c) Posons $w_{n} = u_{n} + 2 v_{n}$. Alors $w_{n+1} = u_{n+1} + 2 v_{n+1} = 2 v_{n} + 2(u_{n} + v_{n}) = 2 u_{n} + 4 v_{n} = 2 (u_{n} + 2 v_{n}) = 2 w_{n}$.
($w_n$) est donc géométrique de raison 2, avec $w_{0} = u_{0} + 2 v_{0} = 1$. Donc $w_{n} = 2^{n}$.
Interprétation : $w_{n} = u_{n} + 2 v_{n}$ est le nombre total de chemins de longueur n partant du sommet 1 (vers 1, ou vers 2, ou vers 3, d'où le facteur 2 devant $v_n$). À chaque étape, depuis un sommet on a exactement 2 choix : le nombre total de chemins de longueur n est donc 2ⁿ, ce qui confirme le calcul.
Vérification pour $n=4$ : $u_{4} + 2 v_{4} = 6 + 10 = 16 = 2^{4}$. Correct.