Degrés, sous-graphe complet, eulérien et chemins via M^n

1. Idée : le degré d'un sommet est le nombre d'arêtes qui y aboutissent. $\deg A=2$ ($AB,AE$), $\deg B=3$ ($AB,BC,BD$), $\deg C=2$ ($BC,CD$), $\deg D=3$ ($BD,CD,DE$), $\deg E=2$ ($AE,DE$). La chaîne $A-B-C-D-E-A$ passe par tous les sommets : $(G)$ est connexe.

2. Idée : une clique d'ordre $k$ impose $k$ couleurs ; $\Delta+1$ en majore toujours le nombre. $BC$, $BD$, $CD$ sont des arêtes : $\{B,C,D\}$ est complet d'ordre $3$, donc $\gamma(G)\geq3$ ; $\Delta=3$ donne $\gamma(G)\leq4$. Coloration : $B\to c_1$, $C\to c_2$, $D\to c_3$, puis $A$ (voisin de $B$ et $E$) $\to c_2$, $E$ (voisin de $A$ et $D$) $\to c_1$ : aucune arête ne joint deux sommets de même couleur. Donc $\boxed{\gamma(G)=3}$.

3. Idée : théorème d'Euler — connexe et $0$ ou $2$ sommets de degré impair. Exactement deux sommets impairs, $B$ et $D$ : il existe une chaîne eulérienne d'extrémités $B$ et $D$, par exemple $B-A-E-D-C-B-D$ (six arêtes, chacune une fois). Pas de cycle eulérien : il faudrait tous les degrés pairs.

4. Idée : $(M^n)_{ij}$ compte les chaînes de longueur $n$ de $i$ à $j$. Le nombre de chemins de longueur $5$ de $D$ vers $B$ est le coefficient de $M^5$ situé ligne $D$ (quatrième ligne), colonne $B$ (deuxième colonne) : $(M^5)_{4,2}$. Le graphe étant non orienté, $M$ est symétrique et ce coefficient égale $(M^5)_{2,4}$.