Định lý năm màu

Định lý năm màu (còn gọi là định lý bản đồ năm màu): Mọi đồ thị phẳng (G) đều có số màu . Là một kết quả từ Lý thuyết đồ thị, cụ thể là mọi bản đồ đều có thể tô bằng năm màu sao cho hai nước nằm kề nhau phải được tô bằng hai màu khác nhau.
Mặc dù đây là định lý yếu hơn định lý bốn màu, nhưng cách chứng minh này cũng đóng vai trò quan trọng bởi vì đây là cơ sở bước đầu để thiết lập cách chứng minh trọn vẹn cho định lý bốn màu mà phải kiểm tra bằng chương trình máy tính.

Dây chuyền luân phiên màu

Giả sử đồ thị phẳng G đã được tô màu các đỉnh. Một dây chuyền luân phiền màu trong G là một dây chuyền sơ cấp mà các đỉnh của chúng được tô bằng 2 màu (trong cách tô màu đang áp dụng cho G).
Giả sử dây chuyền x₀ x₁ x₂... xₖ là dây chuyền luân phiên màu được tô bởi 2 màu W (White) và B (Black) trong cách tô đang dùng cho G. Nếu x₀ được tô bởi W thì x₁ được tô bở B, x₂ được tô bởi W, x₃ được tô bởi B,... Sở dĩ như vậy vì các đỉnh kề nhau phải sử dụng màu khác nhau, mà các đỉnh trên dây chuyền này chỉ được tô bởi W và B.

Tính chất của các dây chuyền luân phiên màu

Vì đang xét biểu diễn phẳng (tức là vẽ trên mặt phẳng sao cho không có bất kỳ 2 cạnh nào cắt nhau)  của đồ thị nên nếu có hai dây chuyền bất kỳ nào đó cắt nhau thì chúng phải có chung đỉnh, tức là cắt nhau tại đỉnh chung chứ không thể có hai cạnh cắt nhau (do cách vẽ biểu diễn phẳng không có bất kỳ hai cạnh nào cắt nhau).
Kết hợp điều này với định nghĩa của dây chuyền luân phiên màu ta suy ra tính chất hiển nhiên nhưng quan trọng sau đây:
Hai dây chuyền luân phiên màu không dùng chung màu thì không thể cắt nhau (vì nếu cắt nhau thì phải có chung đỉnh, mà đỉnh chung đó lại tô một màu nào đó nên hai dây chuyền phải có dùng chung 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ử  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à: .
Chứng minh
Giả sử ngược lại: 
Giả sử đồ thị gồm n đỉnh và e cạnh. Nếu số cạnh  thì điều phải chứng minh là hiển nhiên, ta chỉ xét .
Áp dụng công thức bậc đỉnh số cạnh và :
Theo hệ quả của công thức Euler: 
Từ đó suy ra: 
Như vậy ta có điều mâu thuẫn, tức là giả sử  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ử  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à:

Chứng minh định lý 5 màu

Ta chứng minh qui 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  đề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 x₀ mà 
Gọi G₁ là đồ thị có được từ G bằng cách xóa đi đỉnh x₀. G₁ là đồ thị phẳng có n-1 đỉnh theo giả thiết qui nạp có thể tô G₁ bằng cách dùng không quá 5 màu, giả sử  và xét một cách tô màu G₁ sử dụng s màu. Ta xét các trường hợp sau đây:

Trường hợp 1

Nếu : chỉ cần lấy cách đang tô cho G₁, sau đó tô x₀ bằng một màu khác với các màu đã tô cho G₁, khi đó ta có cách tô màu G sử dụng  màu và suy ra:

Trường hợp 2

Nếu  và : x₀ kề với không quá 4 đỉnh, các đỉnh kề với x₀ sử dụng chưa hết 5 màu, ta lấy cách đang tô cho G₁ và tô x₀ bằng màu khác với các đỉnh xung quanh x₀ (nhưng vẫn nằm trong số 5 màu đang dùng cho G1). Suy ra:

Dạng 2

Tồn tại dây chuyền luân phiên màu Green – White từ đỉnh y₁ đến đỉnh y₄.
Lúc này ta xét sự tồn tại dây chuyền luân phiên màu Blue – Yellow từ y₅ đến y₃: nếu dây chuyền như vậy tồn tại thì theo tính chất liên tục (xem hình) dây chuyền này phải cắt dây chuyền luân phiên màu Green – White: mâu thuẫn với tính chất của dây chuyền luân phiên màu bởi vì 2 dây chuyền này không có chung màu. Như vậy:
Không tồn tại dây chuyền luân phiên màu Blue – Yellow từ đỉnh y₅ đến đỉnh y₃.
Bằng cách lý luận hoàn toàn tương tự như dạng 1, ta có thể thực hiện phép thay thế màu sao cho y₅ chuyển thành Yellow còn y₃ thì vẫn giữ nguyên màu cũ là Yellow. Lúc đó có thể tô x₀ bằng màu Blue, nên đồ thị (G) có thể tô bằng 5 màu.