Luận văn Thạc sĩ Toán học: Luật tương hỗ trong tô màu đồ thị

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:45

Thêm vào BST

Báo xấu

40
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

ài toán tô màu cho các đỉnh (hay các cạnh) của một đồ thị để giải toán là phương pháp khá hay và hấp dẫn của lý thuyết đồ thị. Phương pháp này không đòi hỏi nhiều về khả năng tính toán mà chủ yếu đòi hỏi sự sáng tạo trong việc đưa ra mô hình cụ thể và linh hoạt trong cách tư duy không thể áp dụng một cách máy móc được. Đó là điểm mạnh cũng như cái khó của bài toán tô màu. Mời các bận cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Luật tương hỗ trong tô màu đồ thị

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ——————–o0o——————– ĐINH THỊ VÂN LUẬT TƯƠNG HỖ TRONG TÔ MÀU ĐỒ THỊ LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2017
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ——————–o0o——————– ĐINH THỊ VÂN LUẬT TƯƠNG HỖ TRONG TÔ MÀU ĐỒ THỊ Chuyên ngành: Phương pháp Toán sơ cấp Mã số: 60 46 01 13 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: TS.HOÀNG LÊ TRƯỜNG THÁI NGUYÊN, 2017
iii Mục lục Lời cảm ơn 1 Danh mục các hình vẽ và bảng biểu 2 Mở đầu 4 1 ĐA THỨC MÀU CỦA ĐỒ THỊ 6 1.1. Các khái niệm cơ bản . . . . . . . . . . . . . . . . . . . . . . 6 1.1.1. Đơn đồ thị . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1.2. Các thuật ngữ cơ bản . . . . . . . . . . . . . . . . . . 8 1.1.3. Đường đi, chu trình . . . . . . . . . . . . . . . . . . . 8 1.1.4. Tính liên thông . . . . . . . . . . . . . . . . . . . . . 9 1.1.5. Đồ thị đầy đủ . . . . . . . . . . . . . . . . . . . . . . 10 1.1.6. Đồ thị vòng . . . . . . . . . . . . . . . . . . . . . . . 10 1.1.7. Đồ thị cây . . . . . . . . . . . . . . . . . . . . . . . . 12 1.1.8. Đồ thị Petersen . . . . . . . . . . . . . . . . . . . . 12 1.1.9. Đồ thị hai phần đầy đủ . . . . . . . . . . . . . . . . . 12 1.2. Tô màu đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.2.1. Tô màu thực sự . . . . . . . . . . . . . . . . . . . . . 14 1.2.2. Đồ thị phẳng . . . . . . . . . . . . . . . . . . . . . . 16 1.2.3. Định lí bốn màu . . . . . . . . . . . . . . . . . . . . 17 1.2.4. Đồ thị xóa, co rút . . . . . . . . . . . . . . . . . . . . 17 1.2.5. Mệnh đề . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.2.6. Các ví dụ . . . . . . . . . . . . . . . . . . . . . . . . 21
iv 1.2.7. Hệ quả . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2 Luật tương hỗ của đa thức màu 28 2.1. Định hướng của đồ thị . . . . . . . . . . . . . . . . . . . . . 28 2.2. Đường định hướng . . . . . . . . . . . . . . . . . . . . . . . 29 2.3. Mệnh đề . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.4. Cặp tương thích . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.5. Mệnh đề . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.6. Định lí . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 Kết luận 40 Tài liệu tham khảo 40
1 Lời cảm ơn Luận văn này được thực hiện tại trường Đại học Khoa học - Đại học Thái Nguyên và hoàn thành dưới sự hướng dẫn của Tiến sĩ Hoàng Lê Trường. Tác giả xin trân trọng bày tỏ lòng kính trọng và biết ơn sâu sắc tới thầy, người đã tận tình chỉ bảo, hướng dẫn, động viên khích lệ và tạo điều kiện thuận lợi cho tác giả trong suốt quá trình học tập và nghiên cứu luận văn. Qua bản luận văn này, tác giả xin gửi lời cảm ơn tới Ban Giám hiệu trường Đại học Khoa học - Đại học Thái Nguyên, Ban chủ nhiệm khoa Toán - Tin, cùng các giảng viên đã tham gia giảng dạy và tạo mọi điều kiện tốt nhất để tác giả học tập và nghiên cứu trong suốt thời gian qua. Tác giả cũng xin cảm ơn gia đình, bạn bè, đồng nghiệp và tất cả mọi người đã quan tâm, động viên và giúp đỡ để tác giả có thể hoàn thành luận văn của mình. Tác giả xin chân thành cảm ơn! Thái Nguyên, ngày ... tháng ... năm 2017 Tác giả luận văn Đinh Thị Vân
2 Danh mục các hình vẽ và bảng biểu Hình 1.1:...................................................................................... 6 Hình 1.2:...................................................................................... 6 Hình 1.3:...................................................................................... 8 Hình 1.4:...................................................................................... 9 Hình 1.5:...................................................................................... 10 Hình 1.6:...................................................................................... 10 Hình 1.7:...................................................................................... 11 Hình 1.8:...................................................................................... 12 Hình 1.9:...................................................................................... 12 Hình 1.10:...................................................................................... 14 Hình 1.11:...................................................................................... 15 Hình 1.12:...................................................................................... 17 Hình 1.13:...................................................................................... 18 Hình 1.14:...................................................................................... 19 Hình 1.15:...................................................................................... 19 Hình 1.16:...................................................................................... 20 Hình 1.17:...................................................................................... 20 Hình 1.18:...................................................................................... 21 Bảng đa thức màu............................................................................ 25 Hình 2.1:...................................................................................... 28 Hình 2.2:...................................................................................... 30 Hình 2.3:...................................................................................... 31 Hình 2.4:...................................................................................... 32 Hình 2.5:...................................................................................... 32
3 Hình 2.6:...................................................................................... 32 Hình 2.7:...................................................................................... 34 Hình 2.8...................................................................................... 35
4 Mở đầu Khái niệm lý thuyết đồ thị được nhiều nhà khoa học độc lập nghiên cứu và có nhiều đóng góp trong lĩnh vực toán học ứng dụng. Bài toán tô màu cho các đỉnh (hay các cạnh) của một đồ thị để giải toán là phương pháp khá hay và hấp dẫn của lý thuyết đồ thị. Phương pháp này không đòi hỏi nhiều về khả năng tính toán mà chủ yếu đòi hỏi sự sáng tạo trong việc đưa ra mô hình cụ thể và linh hoạt trong cách tư duy không thể áp dụng một cách máy móc được. Đó là điểm mạnh cũng như cái khó của bài toán tô màu. Mong muốn của tác giả luận văn là có thể cung cấp cho người đọc một cái nhìn tổng quan nhưng cũng khá chi tiết về việc sử dụng tô màu như một nghệ thuật giải toán, hy vọng nó sẽ giúp ích phần nào cho việc bồi dưỡng học sinh chuyên ở các trường THPT, phát triển tư duy cho học sinh, mở ra một hướng nghiên cứu mới cho những ai quan tâm. Lý thuyết đồ thị ra đời và phát triển gắn liền với tên tuổi của nhiều nhà toán học nổi tiếng: Euler (Thụy sĩ), với bài toán về 7 cầu ở thành phố K¨onigsberg, K¨onig và Egevasry (Hungari), với phương pháp Hungari giải bài toán phân việc.Về vấn đề tô màu đồ thị có nhiều kết quả lý thuyết đáng chú ý: Định lý Brooks, Minty về tô màu đỉnh; Định lý K¨onig, Vizing, Shannon về tô màu cạnh, định lý 5 màu của Heawood (1890) và Định lý 4 màu của Appel và Haken (1976), đã giải quyết được giả thuyết 4 màu nổi tiếng do Guthrie nêu ra lần đầu năm 1852. Ứng dụng lí thuyết đồ thị nói chung và bài toán tô màu đồ thị nói
5 riêng để giải các bài toán không muẫu mực, các bài toán thường gặp trong thực tế và một vài bài toán trong các kì thi Toán quốc tế. Với mục tiêu trên, tác giả tiến hành trình bày lại một số kết quả trong cuốn tài liệu tham khảo [1] và luận văn được chia thành hai chương: Chương 1. Đa thức màu của đồ thị Chương 2. Luật tương hỗ của đa thức màu Mặc dù đã có nhiều cố gắng, song do thời gian và trình độ còn hạn chế nên bản luận văn khó tránh khỏi những thiếu sót nhất định. Tác giả rất mong nhận được ý kiến đóng góp của quý độc giả để bản luận văn này được hoàn thiện hơn. Tác giả Đinh Thị Vân
6 Chương 1 ĐA THỨC MÀU CỦA ĐỒ THỊ To many, mathematics is a collection of theorems. For me, mathemat- ics is a collection of examples; a theorem is a statement about a collection of axamples and the purpose of proving theorems is to classify and explain the examples... John B. Conway 1.1. Các khái niệm cơ bản Đồ thị và màu sắc của chúng là thứ yêu thích nhất trong bộ môn toán rời rạc. Và chúng tôi cũng không chống lại sự cám dỗ đó để xuất phát với một trong các ví dụ đẹp nhất. 1.1.1. Đơn đồ thị Định nghĩa 1.1 Đồ thị vô hướng hoặc đồ thị G là một cặp không có thứ tự G = (V, E) trong đó • V là tập hữu hạn khác rỗng mà các phần tử của nó được gọi là các đỉnh (vertex) của G.
7 • E ⊆ V 2 là tập các cặp không sắp thứ tự gồm hai phần tử của V , được gọi là cạnh của đồ thị G. Hai đỉnh thuộc một cạnh được gọi là các đỉnh đầu cuối của cạnh đó. Chính xác hơn, đây là một định nghĩa đồ thị đơn khi chúng ta loại trừ sự tồn tại của nhiều cạnh giữa các đỉnh, đặc biệt cạnh mà có điểm đầu và điểm cuối trùng nhau được gọi là khuyên ví dụ hình 1.1. Hình 1.1: Đồ thị đơn và đồ thị không đơn Ví dụ 1.1 Hình 1.2 là một biểu diễn đồ họa của đồ thị G sau. • V = {a, b, c, d, e, f, h, g} là tập đỉnh của đồ thị G. • E = {ab, ad, bc, bd, bh, cd, hh, hf, hg} là tập cạnh của đồ thị G. Chúng ta thấy rằng đồ thị G có 8 đỉnh và có 9 cạnh. Đỉnh e không thuộc bất kì cạnh nào và những đỉnh như vậy được gọi là đỉnh cô lập của đồ thị G. Trong tập cạnh có cạnh đặc biệt hh, mà chúng ta gọi là khuyên của đồ thị. a e f b c g d h Hình 1.2: Đồ thị G
8 1.1.2. Các thuật ngữ cơ bản a) Kề và liên thuộc Giả sử u và v là hai đỉnh của đồ thị G = (V, E) và e = (u, v) là cạnh của đồ thị, khi đó ta nói: + u và v kề nhau và e liên thuộc với u và v. + Các đỉnh u và v gọi là các đỉnh đầu của cạnh e. +Cạnh e cũng được gọi là cạnh nối các đỉnh u và v. v e u b) Bậc của đỉnh Bậc của đỉnh v trong đồ thị G = (V, E) là số các cạnh liên thuộc với nó, riêng khuyên tại một đỉnh được tính hai lần cho bậc của nó. Ký hiệu deg(v). Đỉnh treo là đỉnh có duy nhất một cạnh liên thuộc với nó v hay deg(v) = 1. Đỉnh cô lập là đỉnh không có cạnh liên thuộc với nó v hay deg(v) = 0.. 1.1.3. Đường đi, chu trình Định nghĩa 1.2 Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n là số nguyên dương, trên đồ thị vô hướng G = (V, E) là dãy x0 := u, x1 , . . . , xn−1 , xn := v, trong đó (xi , xi+1 ) ∈ E, với mọi i = 0, 1, 2, . . . , n−1. Đường đi nói trên còn có thể biểu diễn dưới dạng dãy các cạnh: (x0 , x1 ), (x1 , x2 ), . . . , (xn−1 , xn ). Đỉnh u gọi là đỉnh đầu, còn đỉnh v gọi là đỉnh cuối của đường đi. Đường
9 đi có đỉnh đầu trùng với đỉnh cuối (tức là u = v) được gọi là chu trình. Đường đi hay chu trình được gọi là đơn nếu như không có cạnh nào bị lặp lại. Từ bây giờ trở đi nếu không nói gì chúng ta chỉ xét các đường đi hay chu trình đơn. Ví dụ 1.2 Xét đồ thị G như trong Ví dụ 1.1. Một số đường đi từ đỉnh a đến đỉnh f là a, b, h, f và a, b, h, g, f . Chúng ta thấy có nhiều đường đi từ a đến f và độ dài là khác nhau. Ngay cả khi có cho trước độ dài và và các đỉnh thì có nhiều đường đi khác nhau. Ví dụ hai đường đi có độ dài 4 đi từ đỉnh d đến đỉnh f là d, a, b, h, f và d, c, b, h, f . Đường đi ngắn nhất từ đỉnh d đến đỉnh f là 3 với đường đi cụ thể là d, b, h, f . Mặt khác chúng ta thấy rằng không có đường đi từ a đến e. Chúng ta thấy rằng a, b, c, d, a và a, b, d, a là các chu trình duy nhất mà xuất phát từ a. Tập các chu trình trong đồ thị G là a, b, c, d; a, b, d; b, c, d và f, h, g. Như vậy đồ thị G có ba chu trình độ dài 3 và một chu trình độ dài 4. Xem hình 1.3 một chu trình độ dài 4 được tô bằng màu đỏ và một chu trình độ dài 3 được tô bằng màu xanh. a e f b c g d h Hình 1.3: Đồ thị G 1.1.4. Tính liên thông Định nghĩa 1.3 Một đồ thị được gọi là liên thông nếu có đường đi giữa mọi cặp đỉnh phân biệt của đồ thị.
10 1.1.5. Đồ thị đầy đủ Định nghĩa 1.4 Đồ thị đầy đủ n đỉnh, ký hiệu là Kn , là đơn đồ thị vô hướng mà hai đỉnh phân biệt bất kỳ của nó luôn liền kề. Như vậy, Kn có n(n−1) 2 cạnh và mỗi đỉnh của Kn có bậc là n − 1. Ví dụ 1.3 Hình 1.4 là một biểu diễn đồ họa của đồ thị G = (V, E) trong đó • V = {a, b, c, d} là tập đỉnh của đồ thị G. • E = {ab, bc, cd, da, ac, bd} là tập cạnh của đồ thị G. Chúng ta thấy rằng G là một đơn đồ thị có 4 đỉnh và 6 cạnh. Mặt khác hai đỉnh bất kì của G luôn liền kề nên G được gọi là đồ thị đầy đủ K4 và mỗi đỉnh của nó có bậc đều bằng 3. a b c d Hình 1.4: Đồ thị đầy đủ K4 1.1.6. Đồ thị vòng Định nghĩa 1.5 Đơn đồ thị n đỉnh v1 , v2 , . . . , vn (n ≥ 3) và n cạnh (v1 , v2 ), (v2 , v3 ), . . . , (vn−1 , vn ), (vn , v1 ) được gọi là đồ thị vòng, ký hiệu là Cn . Như vậy, mỗi đỉnh của Cn có bậc là 2. Ví dụ 1.4 Hình 1.5 là một biểu diễn đồ họa của đồ thị G mà chúng ta gọi là đồ thị tam giác.
11 • V = {a, b, c} là tập đỉnh của đồ thị G. • E = {ab, bc, ca} là tập cạnh của đồ thị G. Chúng ta thấy rằng G là một đơn đồ thị có 3 đỉnh và 3 cạnh. Đồ thị tam giác không có đỉnh cô lập và không có khuyên. Hai đỉnh bất kì của đồ thị G luôn liền kề, và bậc của mọi đỉnh trong đồ thị tam giác là 2. Vậy đồ thị tam giác là đồ thị thị vòng và cũng là đồ đầy đủ. a b c Hình 1.5: Đồ thị tam giác Ví dụ 1.5 Hình 1.6 là một biểu diễn đồ họa của đồ thị C4 mà chúng ta gọi là đồ thị hình vuông. • V = {u, v, s, t} là tập đỉnh của đồ thị G. • E = {uv, vs, st, tu} là tập cạnh của đồ thị G. Chúng ta thấy rằng G là một đơn đồ thị có 4 đỉnh là u, v, s, t và 4 cạnh là (u, v), (v, s), (s, t), (t, u). Do đó G là đồ thị vòng và bậc của mọi đỉnh trong đồ thị hình vuông đều bằng 2. Vì đồ thị G có hai cặp đỉnh u và s không liền kề, v và t cũng không liền kề nên G là đồ thị không đầy đủ. u v s t Hình 1.6: Đồ thị hình vuông (hay đồ thị C4 )
12 1.1.7. Đồ thị cây Định nghĩa 1.6 Cây là một đồ thị vô hướng liên thông và không chứa chu trình. Rừng là hợp của nhiều cây. Ví dụ 1.6 Rừng sau có ba cây m l k p a d j b g n o r f c e i q h Hình 1.7: Rừng cây Chúng ta thấy rằng ba đồ thị trong hình 1.7 là ba đồ thị vô hướng liên thông và không có chu trình nên chúng là các cây. 1.1.8. Đồ thị Petersen Định nghĩa 1.7 Đồ thị Petersen là đồ thị vô hướng với 10 đỉnh và 15 cạnh. Ví dụ 1.7 Hình 1.8 là một biểu diễn đồ họa của đồ thị Petersen nó được vẽ như một ngũ giác bao ngoài và hình ngôi sao bên trong với số đỉnh là 10 và số cạnh là 15. 1.1.9. Đồ thị hai phần đầy đủ Định nghĩa 1.8 Đồ thị G = (V, E) sao cho V = V1 ∪ V2 , V1 ∩ V2 = ∅, V1 6= ∅, V2 6= ∅ và mỗi cạnh của G được nối một đỉnh trong V1 và một đỉnh
13 B Hình 1.8: Đồ thị Petersen trong V2 được gọi là đồ thị hai phần. Nếu đồ thị hai phần G = (V1 ∪ V2 , E) sao cho với mọi v1 ∈ V1 , v2 ∈ V2 , (v1 , v2 ) ∈ E thì G được gọi là đồ thị hai phần đầy đủ. Nếu |V1 | = m, |V2 | = n thì đồ thị G được ký hiệu là Km,n . Như vậy, Km,n có mn cạnh, các đỉnh của V1 có bậc n và các đỉnh của V2 có bậc m. Ví dụ 1.8 Hình 1.9 là biểu diễn đồ họa của đồ thị G = (V, E) trong đó • V = {a, b, c, d, e, f } là tập đỉnh của đồ thị G. • E = {ad, ae, af, bd, be, bf, cd, ce, cf } là tập cạnh của đồ thị G. Ta có tập các đỉnh V của đồ thị G được chia thành hai tập rời nhau là V1 = {a, b, c} và V2 = {d, e, f } thỏa mãn mỗi cạnh của đồ thị G được tạo bởi một đỉnh trong V1 với một đỉnh trong V2 và với mọi u ∈ V1 , v ∈ V2 , (u, v) ∈ E, mặt khác |V1 | = 3, |V2 | = 3 nên nó được gọi là đồ thị hai phần đầy đủ K3,3 a d b e c f Hình 1.9: Đồ thị hai phần đầy đủ K3,3
14 1.2. Tô màu đồ thị Chúng ta bắt đầu mục này với khái niệm tô màu đồ thị. 1.2.1. Tô màu thực sự Định nghĩa 1.9 n-màu của một đồ thị G = (V, E) là một ánh xạ c : V → [n] := {1, 2, . . . , n}. n-màu c được gọi là thực sự nếu không có hai đỉnh trên cùng một cạnh được gán cùng màu, tức là c (u) 6= c (v) với mọi uv ∈ E. Ví dụ 1.9 Cho đồ thị tam giác G như trong Ví dụ 1.4. Với n = 2, các cách tô màu của đồ thị G lần lượt là 1. c1 (a) = 1, c1 (b) = 1, c1 (c) = 1 2. c2 (a) = 1, c2 (b) = 1, c2 (c) = 2 3. c3 (a) = 1, c3 (b) = 2, c3 (c) = 1 4. c4 (a) = 1, c4 (b) = 2, c4 (c) = 2 5. c5 (a) = 2, c5 (b) = 1, c5 (c) = 1 6. c6 (a) = 2, c6 (b) = 1, c6 (c) = 2 7. c7 (a) = 2, c7 (b) = 2, c7 (c) = 1 8. c8 (a) = 2, c8 (b) = 2, c8 (c) = 2 Vậy với n = 2 thì đồ thị G có 8 cách tô màu nhưng không có cách tô màu thực sự nào. Với n = 3, các cách tô màu thực của đồ thị G lần lượt là 1. c1 (a) = 1, c1 (b) = 2, c1 (c) = 3 2. c2 (a) = 1, c2 (b) = 3, c2 (c) = 2
15 3. c3 (a) = 2, c3 (b) = 1, c3 (c) = 3 4. c4 (a) = 2, c4 (b) = 3, c4 (c) = 1 5. c5 (a) = 3, c5 (b) = 1, c5 (c) = 2 6. c6 (a) = 3, c6 (b) = 2, c6 (c) = 1 Vậy với n = 3 thì đồ thị G có 6 cách tô màu thực sự. Hình 1.10 là một biểu diễn đồ họa của cách tô màu c1 của đồ thị G a=1 b=2 c=3 Hình 1.10: Tô màu thực sự Ví dụ 1.10 Cho đồ thị hình vuông C4 như hình vẽ. Với n = 2, các cách tô màu thực sự của đồ thị G lần lượt là 1. c1 (u) = 1, c1 (v) = 2, c1 (s) = 1, c1 (t) = 2 2. c2 (u) = 2, c2 (v) = 1, c2 (s) = 2, c2 (t) = 1 Với n=3, các cách tô màu thực sự của đồ thị hình vuông là 1. c1 (u) = 1, c1 (v) = 2, c1 (s) = 1, c1 (t) = 2 2. c2 (u) = 2, c2 (v) = 1, c2 (s) = 2, c2 (t) = 1 3. c3 (u) = 1, c3 (v) = 3, c3 (s) = 1, c3 (t) = 3 4. c4 (u) = 3, c4 (v) = 1, c4 (s) = 3, c4 (t) = 1 5. c5 (u) = 2, c5 (v) = 3, c5 (s) = 2, c5 (t) = 3 6. c6 (u) = 3, c6 (v) = 2, c6 (s) = 3, c6 (t) = 2 7. c7 (u) = 1, c7 (v) = 2, c7 (s) = 3, c7 (t) = 2
16 8. c8 (u) = 1, c8 (v) = 3, c8 (s) = 2, c8 (t) = 3 9. c9 (u) = 2, c9 (v) = 1, c9 (s) = 3, c9 (t) = 1 10. c10 (u) = 2, c10 (v) = 3, c10 (s) = 1, c10 (t) = 3 11. c11 (u) = 3, c11 (v) = 1, c11 (s) = 2, c11 (t) = 1 12. c12 (u) = 3, c12 (v) = 2, c12 (s) = 1, c12 (t) = 2 u=1 v=2 t=2 s=1 Hình 1.11: Một cách tô màu thực sự của đồ thị hình vuông Thuật ngữ "màu" xuất phát từ việc giải thích ý nghĩa tự nhiên của c(v), vì một trong n màu có thể được tô cho đỉnh v. Một cách tô màu thực sự là mỗi đỉnh có màu khác màu của các đỉnh kề với nó. Đây là dấu hiệu đầu tiên tại sao các đồ thị đơn thường thỏa mãn: sự tồn tại và số lượng n-màu không ảnh hưởng bởi các cạnh song song, và ở đó không có tô màu thực sự với sự xuất hiện của khuyên. Phần lớn sự nổi tiếng của bài toán tô màu đồ thị xuất phát từ câu hỏi được đặt ra vào năm 1850 bởi Francis Guthric và được trả lời sau 124 năm. Để dưa ra câu hỏi trong điều kiện hiện tại, chúng ta cần định nghĩa sau. 1.2.2. Đồ thị phẳng Định nghĩa 1.10 Đồ thị G được gọi là đồ thị phẳng nếu G được vẽ trong mặt phẳng sao cho các cạnh không cắt nhau ngoại trừ tại các đỉnh.