Exercice 11, § 2

Soit G un graphe connexe dont l’ensemble S des sommets n’est pas vide. On appelle diamètre de G le diamètre diam(G) de l’espace métrique $(S, d_G)$. a) Démontrer que diam(G) $\leqslant$ Card(S)$-1$. Pour quels graphes cette inégalité est-elle une égalité ?

b) Soit $v$ un entier $\geqslant 2$ tel que tout sommet de G soit de degré au plus $v$. Démontrer que Card(S) $\leqslant v^{diam(G)}$. Pour quels graphes cette inégalité est-elle une égalité ? c) Soit $n$ un entier tel que $n\geqslant 2$. Soit $T_n$ la partie de $\mathfrak{S}_n$ formée des transpositions de support $\{m, m+ 1\}$, pour $m\in \{1, . . . , n-1\}$. Démontrer que le diamètre du graphe de Cayley $\mathscr{G}(\mathfrak{S}_n,T_n)$ est égal à $n(n-1)/2$.

d) Soit $n$ un entier tel que $n\geqslant 2$. Soient $\tau$ la transposition de support $\{1,2\}$ et $\sigma$ le cycle $(1,2, . . . , n)\mapsto (2,3, . . . , n,1)$ dans le groupe $\mathfrak{S}_n$. Soit alors $G_n$ le graphe de Cayley $\mathscr{G}(\mathfrak{S}_n,\{\sigma , \tau \})$. Démontrer que $n(n-1)/6\leqslant$ diam(G$_n$)$\leqslant 3n(n-1)/2$. (Soit T l’ensemble des suites $(x, y, z)$ d’éléments de $\{1, . . . , n\}$ telles que $x < y < z$. Si $t= (x, y, z)\in T$, on dit qu’une permutation $\lambda \in \mathfrak{S}_n$ préserve l’ordre cyclique de $t$ si l’on a $\lambda (x)< \lambda (y)< \lambda (z)$, ou $\lambda (y)< \lambda (z)< \lambda (x)$, ou $\lambda (z)< \lambda (x)< \lambda (y)$. Observer que la permutation $\sigma$ préserve l’ordre cyclique de tout élément de T, et que la permutation $\tau$ préserve l’ordre cyclique de tout élément de T qui n’est pas de la forme $(1,2, x)$. En déduire que la distance de la permutation identique à la permutation $(1, . . . , n)\mapsto (n, n-1, . . . ,1)$ est au moins égale à $n(n-1)/6$.)