Câu hỏi 43
Có các đỉnh $n$ trên một mặt phẳng. Đồ thị $G$ được hình thành bằng cách nối mỗi hai đỉnh bằng chính xác một cạnh và tô tất cả các cạnh, mỗi cạnh bằng một màu, được chọn từ các màu đã cho của $k$.
a. Đối với $n = 6$ và $k = 3$, hãy chứng minh rằng có thể sơn các cạnh sao cho đồ thị không chứa mạch kín chỉ được sơn một màu.
b. Chứng minh rằng với mọi giá trị nguyên dương của $k$ (tức là số lượng màu cho phép), nếu số đỉnh là $n \ge 2k+1$ thì luôn có thể tìm được mạch kín một màu trong $G$.
a. Đối với $n = 6$ và $k = 3$, hãy chứng minh rằng có thể sơn các cạnh sao cho đồ thị không chứa mạch kín chỉ được sơn một màu.
b. Chứng minh rằng với mọi giá trị nguyên dương của $k$ (tức là số lượng màu cho phép), nếu số đỉnh là $n \ge 2k+1$ thì luôn có thể tìm được mạch kín một màu trong $G$.