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

Idée : le critère d'Euler porte sur la parité des degrés. Un graphe connexe possédant exactement deux sommets de degré impair admet une chaîne eulérienne (elle part de l'un de ces sommets et arrive à l'autre) : oui. Un cycle eulérien exige que tous les degrés soient pairs (on entre et on sort de chaque sommet autant de fois) : non ici. Ajouter une arête entre les deux sommets impairs rendrait tous les degrés pairs et créerait un cycle eulérien.

1.a Idée : compter les arêtes qui aboutissent à chaque sommet.

Contrôle : la somme des degrés vaut $20=2\times10$, deux fois le nombre d'arêtes.

1.b Idée : théorème d'Euler — un graphe connexe dont exactement deux sommets sont de degré impair admet une chaîne eulérienne joignant ces deux sommets. $(G)$ est connexe et seuls $A$ et $F$ sont de degré impair : $(G)$ admet une chaîne eulérienne d'extrémités $A$ et $F$, par exemple $A-B-D-A-C-E-B-F-D-E-F$.

1.c Non : un cycle eulérien exige que tous les degrés soient pairs, or $\deg A=\deg F=3$.

2.a Les six arêtes $BD$, $BE$, $BF$, $DE$, $DF$ et $EF$ existent : $\{B,D,E,F\}$ est un sous-graphe complet d'ordre $4$.

2.b Idée : un sous-graphe complet d'ordre $p$ impose $p$ couleurs ; le degré maximal $\Delta$ donne $\gamma\le\Delta+1$. Les quatre sommets $B$, $D$, $E$, $F$ sont deux à deux adjacents, donc $\gamma(G)\ge4$. Le plus grand degré est $\Delta=4$, donc $\gamma(G)\le4+1=5$. Ainsi $4\le\gamma(G)\le5$.

2.c Idée : une coloration à $4$ couleurs suffit pour conclure. On colore $B$, $D$, $E$, $F$ avec $c_1$, $c_2$, $c_3$, $c_4$. $A$ est voisin de $B$, $C$, $D$ mais pas de $E$ : il reçoit $c_3$. $C$ est voisin de $A$ et $E$ mais pas de $B$ : il reçoit $c_1$. Aucune arête ne relie deux sommets de même couleur, donc $\boxed{\gamma(G)=4}$.

3.a $a_{63}$ est le coefficient de la ligne $F$ (sixième) et de la colonne $C$ (troisième) : $a_{63}=0$, car il n'y a pas d'arête entre $F$ et $C$. Dans le contexte : les clubs $F$ et $C$ n'ont aucun membre en commun.

3.b Idée : le graphe n'est pas orienté, donc $M$ est symétrique ($a_{ij}=a_{ji}$) ; on complète le triangle supérieur par symétrie.

4. Idée : les clubs sont les sommets, les journées sont les couleurs ; deux clubs reliés doivent avoir des journées différentes. Le nombre minimal de journées est $\gamma(G)=4$. La coloration de 2.c donne un planning : jour 1, clubs $B$ et $C$ ; jour 2, club $D$ ; jour 3, clubs $A$ et $E$ ; jour 4, club $F$.

5. Le nombre cherché est $(M^3)_{23}=\boxed{3}$ (ligne $B$, colonne $C$). Idée : pour les citer, regarder par où l'on arrive en $C$ : ses voisins sont $A$ et $E$. Pour finir par $A-C$, il faut un voisin commun de $B$ et $A$ : $D$. Pour finir par $E-C$, un voisin commun de $B$ et $E$ : $D$ ou $F$. Les chaînes sont $B-D-A-C$, $B-D-E-C$, $B-F-E-C$.

1. $(M^5)_{42}=\boxed{2}$ (ligne $D$, colonne $B$). Idée : pour les citer, lire $M$. La seule flèche qui sort de $D$ est $D\to A$ (ligne $D$ de $M$), et la seule qui arrive en $B$ est $A\to B$ (colonne $B$). Il reste un circuit de longueur $3$ de $A$ à $A$ : $A\to E\to C\to A$ ou $A\to E\to D\to A$. Les chaînes sont $D\to A\to E\to C\to A\to B$ et $D\to A\to E\to D\to A\to B$.

2. Idée : une chaîne fermée de longueur $5$ part d'un sommet et y revient ; celles qui partent du $i$-ème sommet sont comptées par $(M^5)_{ii}$, donc on additionne les coefficients de la diagonale.

Il y a $\boxed{40}$ chaînes fermées de longueur $5$ ; par exemple $A\to B\to A\to E\to C\to A$.

3. Ce sont celles que compte le premier coefficient diagonal : $(M^5)_{11}=14$.

1. $(M^2)_{36}=1$ : une seule chaîne, $C-D-F$ ($D$ est le seul voisin commun de $C$ et de $F$).

2. Idée : « longueur inférieure ou égale à $3$ » regroupe les longueurs $1$, $2$ et $3$ ; on additionne les coefficients $(C,F)$ de $M$, $M^2$ et $M^3$. $m_{36}=1$ (l'arête $C-F$), $(M^2)_{36}=1$ et $(M^3)_{36}=6$ :

Il y a $\boxed{8}$ chaînes de longueur au plus $3$ reliant $C$ à $F$.

3. Par exemple $C-B-D-F$ : les arêtes $C-B$, $B-D$ et $D-F$ existent.

1.

La somme des degrés vaut $18=2\times9$.

2. Idée : $(M^2)_{ii}$ compte les chaînes de longueur $2$ qui partent de $i$ et y reviennent, c'est-à-dire les allers-retours $i-j-i$ : il y en a une par voisin, donc $(M^2)_{ii}=\deg i$. Les deux matrices sont symétriques, ce qui ne permet pas de conclure. La diagonale de $P$ est $(2,4,3,2,4,3)$, exactement la liste des degrés ; celle de $Q$ est $(2,4,3,2,3,4)$, et $q_{55}=3\neq\deg E=4$. Donc $Q\neq M^2$ et $\boxed{M^2=P}$.

3. $p_{24}=2$ : il y a deux chaînes de longueur $2$ de $B$ à $D$, qui passent par les voisins communs de $B$ et de $D$ : $B-C-D$ et $B-E-D$.

1. $(M^3)_{15}=2$. Les voisins de $E$ sont $B$ et $D$ ; une chaîne $A-x-B-E$ exige un voisin commun $x$ de $A$ et $B$ : $C$ ; une chaîne $A-x-D-E$ un voisin commun de $A$ et $D$ : $C$. Ce sont $A-C-B-E$ et $A-C-D-E$.

2. Idée : $M^4=M^3\times M$, donc $(M^4)_{15}$ est le produit de la ligne $A$ de $M^3$ par la colonne $E$ de $M$.

Ce produit vaut $7+7=\boxed{14}$. Lecture : une chaîne de longueur $4$ de $A$ à $E$ se termine par l'arête $B-E$ ou $D-E$ ; il y a $7$ chaînes de longueur $3$ de $A$ à $B$ et $7$ de $A$ à $D$.

3. Par exemple $A-B-C-D-E$ : ses quatre arêtes existent.

1. a) L'ordre est le nombre de sommets, soit le nombre de lignes de $M$ : $6$.

2. a) La somme des coefficients de $M$ vaut $16$ ; chaque arête y est comptée deux fois ($m_{ij}=m_{ji}=1$) : $G$ a $8$ arêtes.

3. b) Les sommes des lignes donnent les degrés $2,2,3,3,2,4$ : seuls $C$ et $D$ sont de degré impair. $G$ est connexe (la chaîne $A-D-C-E-B-F$ passe par tous les sommets) : il admet une chaîne eulérienne d'extrémités $C$ et $D$, mais pas de cycle eulérien. Il n'est pas complet : $m_{12}=0$, $A$ et $B$ ne sont pas adjacents.

4. c) Les voisins de $A$ sont $D$ et $F$, ceux de $C$ sont $D$, $E$ et $F$ : deux voisins communs, donc deux chaînes, $A-D-C$ et $A-F-C$ (c'est le coefficient $(M^2)_{13}=2$).