1761561
Định lý năm màu
https://vi.wikipedia.org/wiki?curid=1761561
Title: Định lý năm màu
Sau đây là một mệnh đề quan trọng liên quan đến "đồ thị phẳng", được sử dụng để chứng minh định lý 5 màu.
Mệnh đề 1.
Giả sử formula_2 là đồ thị đơn, phẳng, liên thông. Khi đó G phải có chứa ít nhất một "đỉnh" có "bậc" nhỏ hơn hay bằng 5.
Tức là: formula_3.
Chứng minh
Giả sử ngược lại: formula_4
Giả sử đồ thị gồm n "đỉnh" và e "cạnh". Nếu số cạnh formula_5 thì điều phải chứng minh là hiển nhiên, ta chỉ xét formula_6.
Áp dụng công thức bậc đỉnh số cạnh và formula_7:
formula_8
Theo hệ quả của công thức Euler: formula_9
Từ đó suy ra: formula_10
Như vậy ta có điều mâu thuẫn, tức là giả sử formula_11 bị sai.
Nhận xét
Mặc dù mệnh đề trên giả sử G là đồ thị đơn, phẳng, liên thông, nhưng nếu G (là đồ thị đơn và phẳng) không liên thông thì mỗi thành phần liên thông của G là đồ thị đơn, phẳng, liên thông: áp dụng mệnh đề trên thì tồn tại "đỉnh" trong thành phần liên thông (cũng là đỉnh của G) có bậc không quá 5.
Như vậy, chúng ta có mệnh đề sau đây.
Mệnh đề 2.
Giả sử formula_2 là đồ thị đơn, phẳng. Khi đó G phải có chứa ít nhất một "đỉnh" có "bậc" nhỏ hơn hay bằng 5.
Tức là: formula_3
Chứng minh định lý 5 màu.
Ta chứng minh quy nạp theo số đỉnh n của đồ thị.
Với n = 1, 2, 3, 4, 5 thì hiển nhiên có thể dùng không quá 5 màu để tô màu các đỉnh theo phép tô màu.
Giả sử rằng mọi đồ thị phẳng có số đỉnh formula_14 đều có thể tô màu "đỉnh" bằng cách dùng không quá 5 màu.
Theo mệnh đề trên G phải chứa một đỉnh x0 mà formula_15