Câu hỏi 39
Cho một đồ thị liên thông có $n$ cạnh, trong đó hai đỉnh bất kỳ được nối bởi nhiều nhất một cạnh. Với hai chu trình bất kỳ $C$ và $C'$ của đồ thị này, định nghĩa **chu trình ngoài** của chúng là
$$
C \star C' = \{x \mid x \in (C - C') \cup (C' - C)\}.
$$
(1) Gọi $r$ là số nguyên dương lớn nhất sao cho ta có thể chọn ra $r$ chu trình $C_1, C_2, \dots, C_r$ của đồ thị sao cho với mọi $1 \le k \le r$ và mọi $1 \le i, j_1, j_2, \dots, j_k \le r$ với $i \notin \{j_1, \dots, j_k\}$, ta có
$$
C_i \neq C_{j_1} \star C_{j_2} \star \dots \star C_{j_k}.
$$
(2) Gọi $s$ là số nguyên dương lớn nhất sao cho ta có thể chọn ra $s$ cạnh trong $n$ cạnh này mà các cạnh được chọn không chứa chu trình nào.
Chứng minh rằng $r+s=n$.
Chú thích: một chu trình là một tập các cạnh có dạng $\{A_i A_{i+1}\}, 1 \le i \le n$, trong đó $n \ge 3$, $A_1, A_2, \dots, A_n$ là các đỉnh phân biệt, và $A_{n+1} = A_1$.
$$
C \star C' = \{x \mid x \in (C - C') \cup (C' - C)\}.
$$
(1) Gọi $r$ là số nguyên dương lớn nhất sao cho ta có thể chọn ra $r$ chu trình $C_1, C_2, \dots, C_r$ của đồ thị sao cho với mọi $1 \le k \le r$ và mọi $1 \le i, j_1, j_2, \dots, j_k \le r$ với $i \notin \{j_1, \dots, j_k\}$, ta có
$$
C_i \neq C_{j_1} \star C_{j_2} \star \dots \star C_{j_k}.
$$
(2) Gọi $s$ là số nguyên dương lớn nhất sao cho ta có thể chọn ra $s$ cạnh trong $n$ cạnh này mà các cạnh được chọn không chứa chu trình nào.
Chứng minh rằng $r+s=n$.
Chú thích: một chu trình là một tập các cạnh có dạng $\{A_i A_{i+1}\}, 1 \le i \le n$, trong đó $n \ge 3$, $A_1, A_2, \dots, A_n$ là các đỉnh phân biệt, và $A_{n+1} = A_1$.