Bài tập 11, § 2

Cho G là một đồ thị liên thông mà tập hợp S các đỉnh là không rỗng. Đường kính của G được định nghĩa là đường kính diam(G) của không gian metric $(S, d_G)$. a) Chứng minh rằng diam(G) $\leqslant$ Card(S)$-1$. Với những đồ thị nào thì bất đẳng thức này là một đẳng thức?

b) Cho $v$ là một số nguyên $\geqslant 2$ sao cho mọi đỉnh của G đều có bậc nhiều nhất là $v$. Chứng minh rằng Card(S) $\leqslant v^{diam(G)}$. Với những đồ thị nào thì bất đẳng thức này là một đẳng thức? c) Cho $n$ là một số nguyên sao cho $n\geqslant 2$. Cho $T_n$ là tập con của $\mathfrak{S}_n$ tạo bởi các phép đổi chỗ có giá đỡ $\{m, m+ 1\}$, với $m\in \{1, . . . , n-1\}$. Chứng minh rằng đường kính của đồ thị Cayley $\mathscr{G}(\mathfrak{S}_n,T_n)$ bằng $n(n-1)/2$.

d) Cho $n$ là một số nguyên sao cho $n\geqslant 2$. Cho $\tau$ là phép đổi chỗ có giá đỡ $\{1,2\}$ và $\sigma$ là chu trình $(1,2, . . . , n)\mapsto (2,3, . . . , n,1)$ trong nhóm $\mathfrak{S}_n$. Khi đó cho $G_n$ là đồ thị Cayley $\mathscr{G}(\mathfrak{S}_n,\{\sigma , \tau \})$. Chứng minh rằng $n(n-1)/6\leqslant$ diam(G$_n$)$\leqslant 3n(n-1)/2$. (Cho T là tập hợp các bộ ba $(x, y, z)$ gồm các phần tử của $\{1, . . . , n\}$ sao cho $x < y < z$. Nếu $t= (x, y, z)\in T$, ta nói rằng một hoán vị $\lambda \in \mathfrak{S}_n$ bảo toàn thứ tự cyclic của $t$ nếu ta có $\lambda (x)< \lambda (y)< \lambda (z)$, hoặc $\lambda (y)< \lambda (z)< \lambda (x)$, hoặc $\lambda (z)< \lambda (x)< \lambda (y)$. Hãy nhận thấy rằng hoán vị $\sigma$ bảo toàn thứ tự cyclic của mọi phần tử của T, và hoán vị $\tau$ bảo toàn thứ tự cyclic của mọi phần tử của T không có dạng $(1,2, x)$. Suy ra rằng khoảng cách từ hoán vị đồng nhất đến hoán vị $(1, . . . , n)\mapsto (n, n-1, . . . ,1)$ ít nhất bằng $n(n-1)/6$.)