Exercise 11, § 2

Let G be a connected graph whose set S of vertices is not empty. The diameter of G is defined to be the diameter diam(G) of the metric space $(S, d_G)$. a) Prove that diam(G) $\leqslant$ Card(S)$-1$. For which graphs is this inequality an equality?

b) Let $v$ be an integer $\geqslant 2$ such that every vertex of G has degree at most $v$. Prove that Card(S) $\leqslant v^{diam(G)}$. For which graphs is this inequality an equality? c) Let $n$ be an integer such that $n\geqslant 2$. Let $T_n$ be the subset of $\mathfrak{S}_n$ formed by the transpositions with support $\{m, m+ 1\}$, for $m\in \{1, . . . , n-1\}$. Prove that the diameter of the Cayley graph $\mathscr{G}(\mathfrak{S}_n,T_n)$ is equal to $n(n-1)/2$.

d) Let $n$ be an integer such that $n\geqslant 2$. Let $\tau$ be the transposition with support $\{1,2\}$ and $\sigma$ the cycle $(1,2, . . . , n)\mapsto (2,3, . . . , n,1)$ in the group $\mathfrak{S}_n$. Let then $G_n$ be the Cayley graph $\mathscr{G}(\mathfrak{S}_n,\{\sigma , \tau \})$. Prove that $n(n-1)/6\leqslant$ diam(G$_n$)$\leqslant 3n(n-1)/2$. (Let T be the set of triples $(x, y, z)$ of elements of $\{1, . . . , n\}$ such that $x < y < z$. If $t= (x, y, z)\in T$, we say that a permutation $\lambda \in \mathfrak{S}_n$ preserves the cyclic order of $t$ if we have $\lambda (x)< \lambda (y)< \lambda (z)$, or $\lambda (y)< \lambda (z)< \lambda (x)$, or $\lambda (z)< \lambda (x)< \lambda (y)$. Observe that the permutation $\sigma$ preserves the cyclic order of every element of T, and that the permutation $\tau$ preserves the cyclic order of every element of T which is not of the form $(1,2, x)$. Deduce that the distance from the identity permutation to the permutation $(1, . . . , n)\mapsto (n, n-1, . . . ,1)$ is at least equal to $n(n-1)/6$.)