Bài tập 8, § 2

Một đường đi $(a_0, f_1, . . . , f_n, a_n)$ trong một đồ thị G được gọi là hamilton nếu, với mọi đỉnh $s$ của G, tồn tại duy nhất một số nguyên $m\in \{1, . . . , n\}$ sao cho $a_m=s$. Một đồ thị được gọi là hamilton nếu tồn tại một đường đi hamilton trong G.

a) Cho S là một tập hợp hữu hạn có lực lượng $\geqslant 3$ và cho $K_S$ là một đồ thị đầy đủ có tập hợp các đỉnh là S. Chứng minh rằng đồ thị $K_S$ là hamilton. Chính xác hơn, chứng minh rằng với mọi định hướng A của G, tồn tại một đường đi hamilton trong $K_S$ mà mọi cung của nó đều thuộc A.

b) Ký hiệu $\mathscr{G}_S$ là tập hợp các đồ thị con của $K_S$ có tập hợp các đỉnh bằng S. Gọi $\preccurlyeq$ là quan hệ thứ tự tốt nhất trong tập hợp $\mathscr{G}_S$ sao cho $G\preccurlyeq G'$ nếu tồn tại các phần tử $u, v$ của S sao cho deg($u$) $+$ deg($v$)$\geqslant$ Card(S) và sao cho Fl(G$'$) là hợp của Fl(G) và hai cung của $K_S$ có các đầu mút là $u$ và $v$.

Chứng minh rằng, với mọi $G\in \mathscr{G}_S$, tập hợp các phần tử H của $\mathscr{G}_S$ sao cho $G\preccurlyeq H$ có một phần tử cực đại duy nhất; ký hiệu nó là $c(G)$.

c) Cho G là một đồ thị con của $K_S$ có tập hợp các đỉnh là S. Chứng minh rằng đồ thị G là hamilton khi và chỉ khi đồ thị $c(G)$ là hamilton. d) Cho G là một đồ thị con của $K_S$ có tập hợp các đỉnh là S và có bậc tại mỗi đỉnh là $\geqslant$ Card(S)$/2$. Chứng minh rằng $c(G)$ bằng $K_S$. Suy ra rằng G là một đồ thị hamilton (định lý của G. Dirac).