ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
VŨ

HOÀNG

LINH
BÀI

TOÁN

TÔ

MÀU
ĐỒ THỊ VÀ ỨNG DỤNG BÀI

TOÁN

TÔ

MÀU
ĐỒ THỊ VÀ ỨNG DỤNG Chuyên ngành: Toán ứng dụng
Mã số: 60 46 01 12

LUẬN VĂN THẠC SĨ TOÁN HỌC

NGƯỜI HƯỚNG DẪN KHOA HỌC

thị và các dạng đồ thị thường gặp, về bài toán tô màu trên đồ thị (tô đỉnh, tô cạnh
và tô diện - tô màu bản đồ) và một số ứng dụng của các bài toán này. Trình bày các
kết quả lý thuyết, các định lý về tô màu trên các loại đồ thị khác nhau và các thuật
toán tô màu đỉnh và cạnh, dựa trên các kết quả lý thuyết đã có.
Nội dung luận văn được viết trong hai chương.

2
Chương 1 "Khái niệm cơ bản về đồ thị" nhắc lại các khái niệm cơ bản về đồ
thị: đỉnh, cạnh, bậc của đỉnh, đồ thị vô hướng và đồ thị có hướng, đường đi và chu
trình, đồ thị liên thông, không liên thông, các phép toán trên đồ thị. Miêu tả nhiều
dạng đồ thị đặc biệt: rừng và cây, đồ thị hình sao, đồ thị vòng, đồ thị đường, đồ thị
bánh xe, đồ thị đầy đủ, đồ thị hai phần, đồ thị hai phần đầy đủ, đồ thị đều (chính
qui), đồ thị Petersen, đồ thị Platon, đồ thị phẳng,
Chương 2 "Bài toán tô màu đồ thị" đề cập tới vấn đề tô màu các đỉnh, cạnh và
diện của một đồ thị. Trình bày các kết quả về tô màu đỉnh: định lý Brooks (1941),
định lý Minty (1962), các định lý tô màu đồ thị phảng, đặc biệt định lý bốn màu
(Appel và Haken, 1976). Về tô màu bản đồ (tô diện của đồ thị phẳng) có các định
lý về bản đồ 2 màu, bản đồ lập phương 3 màu và định lý bốn màu cho bản đồ. Về
tô màu cạnh của đồ thị: trình bày định lý Vizing (1964) về số màu tối thiểu cần tô,
định lý tô cạnh đồ thị đầy đủ, tô cạnh đồ thị hai phần (Định lý König, 1916) và
quan hệ với định lý bốn màu. Cuối chương đề cập tới đa thức màu, cho biết có thể
tô đỉnh của đò thị bằng k màu được không, nếu được thì có mấy cách tô.
Nhân dịp này, tác giả luận văn xin bày tỏ lòng biết ơn sâu sắc tới GS

-

TS Trần
Vũ Thiệu, đã tận tình giúp đỡ trong suốt quá trình làm luận văn. Tác giả chân thành
cảm ơn các thầy giáo, cô giáo Trường Đại học Khoa học - Đại học Thái Nguyên,
Viện Toán hoc - Viện Hàn lâm Khoa học và Công nghệ Việt Nam đã giảng dạy và

(v, w) hay đơn giản là vw (v và w có thể là các chữ số). Một cạnh có dạng (a, a),
nối đỉnh a với chính nó, gọi là một khuyên (loop).
Nếu đồ thị G có tập đỉnh là V và tập cạnh là E ⊆ V

×

V thì để cho gọn, ta viết
G = (V, E). Ta cũng dùng ký hiệu V(G) để chỉ tập đỉnh và E(G) để chỉ tập cạnh của
đồ thị G. Ký hiệu n = |V(G)| là số đỉnh và m = |E(G)| là số cạnh của đồ thị G.
4
Để dễ hình dung, mỗi đồ thị thường được biểu diễn bởi một hình vẽ trên mặt
phẳng. Chẳng hạn, Hình 1.3 biểu diễn một đồ thị có 5 đỉnh: P, Q, R, S, T và 8 cạnh
(mỗi cạnh là một đoạn thẳng nối hai đỉnh). Chú ý rằng điểm cắt nhau của hai cạnh
PS và QT trong hình vẽ không phải là một đỉnh của đồ thị.
Đỉnh v gọi là kề (adjacent) đỉnh w nếu có một cạnh của đồ thị nối v với w.
Nếu ký hiệu cạnh này là e thì ta viết e = (v,

w) và nói cạnh e liên thuộc (incident) v,
w hay v, w là hai đầu mút của e. Cạnh e và e' gọi là kề nhau nếu e, e' có chung đỉnh.
Hai cạnh e và e' cùng nối một cặp đỉnh gọi là cạnh kép (multiple edge). Đồ thị
không có cạnh kép gọi là một đơn đồ thị (simple graph). Trái lại, gọi là một đa đồ
thị. Hình 1.4 và 1.5 minh họa cạnh kép và khuyên trong đa đồ thị.

Hình 1.4. Cạnh kép và đa đồ thị Hình 1.5. Khuyên trong đa đồ thị
Một cạnh của đồ thị gọi là cạnh có hướng (directed edge) nếu có qui định rõ
một đầu mút của cạnh là đỉnh đầu, mút kia là đỉnh cuối. Cạnh có hướng còn được
gọi là một cung.

Sau đây ta tập trung chủ yếu xét các đồ thị vô hướng và một số phép toán.
• Đồ thị con (subgraph) của một đồ thị G là đồ thị nhận được từ G bằng cách
bỏ đi một số đỉnh và một số cạnh của nó. Nói chính xác, H = (V(H), E(H)) là một
đồ thị con của G nếu V(H) V(G) và E(H) E(G). Ta cũng nói G chứa H. H gọi
là đồ thị con cảm sinh (induced subgraph) của G nếu H là một đồ thị con của G và
E(H) = {(x, y) ∈ E(G) : x, y ∈ V(H)}. Ở đây H là đồ thị con của G sinh bởi V(H).
Vì thế ta còn viết H = G[V(H)]. Đồ thị con H của G gọi là đồ thị con bao trùm nếu
V(H) = V(G), tức tập đỉnh của H và của G trùng nhau.
• Với v ∈ V(G), ký hiệu G - v là đồ thị con của G cảm sinh bởi V(G) \ {v},
tức đồ thị nhận được từ G bằng cách bỏ đỉnh v và các cạnh liên thuộc v.
• Với e ∈ E(G), ta định nghĩa G - e := (V(G), E(G) \ {e}), tức đồ thị nhận
được từ G bằng cách xóa cạnh e (không xóa hai đầu mút của e). Ta cũng định nghĩa
6
G \ e là đồ thị nhận được bằng cách co cạnh e thành một điểm duy nhất. Hình 1.8
minh họa các đồ thị G, G - e và G \ e.

Hình 1.8. Đồ thị G, cạnh e và các đồ thị G e và G \ e tương ứng
1.1.3. Đồ thị đẳng cấu
Hai đồ thị G
1
và G
2
gọi là đẳng cấu (isomorphic) nếu chúng có số đỉnh và số
cạnh như nhau và có phép tương ứng một

-


)

∩V(G
2
) = ∅. Khi đó, hợp (union) G
1
∪ G
2
là đồ thị
có tập đỉnh là V(G
1
) ∪ V(G
2
) và tập cạnh là E(G
1
) ∪ E(G
2
) (Hình 1.10). Hình 1.10. Đồ thị G
1
, G
2
và hợp G
1
∪ G
2
Hình 1.11. Đồ thị không liên thông


chứng minh kết quả tương ứng cho các đồ thị liên thông, sau đó áp dụng kết quả
thu được cho từng thành phần liên thông riêng lẻ của đồ thị. Một bảng gồm tất cả
các đồ thị liên thông (không ghi tên đỉnh) có tối đa 5 đỉnh được vẽ ở Hình 1.12.
1.1.5. Đường và chu trình trong đồ thị vô hướng
Đường (path) P từ đỉnh v tới đỉnh w là một dãy liên tiếp các cạnh có dạng:
(a
0
, a
1
), (a
1
, a
2
), , (a
k-1
, a
k
) với (a
i-1
, a
i
) E(G), a
0
= v, a
k
= w và k 1,
trong đó các đỉnh a
0
, a
1

Một cách biểu diễn hữu ích khác là dùng các ma trận.
y
u
v
w
x
u : v, y
v : u, w, y
w: v, x, y
x w, y
y : u, v, w, x
∙
∙
∙
∙
9
• Ma trận kề: Nếu G là một đồ thị với các đỉnh được đánh số 1, 2, … , n, thì
ma trận kề (adjacency matrrix) cuả G là ma trận vuông A cấp n, phần tử ở hàng i
cột j của A bằng số cạnh nối đỉnh i và đỉnh j của đồ thị.
• Ma trận liên thuộc: Nếu các cạnh của đồ thị cũng được đánh số 1, 2, … , m,
thì ma trận liên thuộc (incidence matrrix) của G là ma trận chữ nhật M cấp n×m,
phần tử ở hàng i cột j của M bằng 1 nếu đỉnh i kề cạnh j và bằng 0 nếu trái lại.
Hình 1.15 vẽ đồ thị G cùng với ma trận kề và ma trận liên thuộc của nó.

Hình 1.15. Ma trận kề và ma trận liên thuộc
1.2. MỘT SỐ DẠNG ĐỒ THỊ ĐẶC BIỆT
Mục này trình bày một số dạng đồ thị đặc biệt, đáng chú ý và hay được dùng

-

1 cạnh, trong
một cây, bao giờ cũng có một đường đi duy nhất nối một cặp đỉnh bất kỳ của cây.
Các ví dụ về rừng và cây được vẽ ở Hình 1.16. Hình 1.16. Ví dụ về rừng và cây
1.2.3. Đồ thị đầy đủ
Một đơn đồ thị trong đó mọi cặp đỉnh (khác nhau) đều kề nhau, gọi là một đồ
thị đầy đủ (completed graph). Đồ thị đầy đủ n đỉnh ký hiệu là K
n
. Số cạnh của K
n

bằng n(n

-

1)/2. Đồ thị K
4
và K
5
được vẽ ở Hình 1.17.

được vẽ ở Hình 1.18.
Hình 1.18. Đồ thị vòng C
6
, đồ thị đường P
6
và đồ thị bánh xe W
6

1.2.5. Đồ thị đều (đồ thị chính qui)
Một đồ thị mà mọi đỉnh có bậc bằng nhau gọi là một đồ thị đều hay đồ thị
chính qui (regular graph). Nếu mọi đỉnh có bậc r thì đồ thị được gọi là đồ thị đều
(chính qui) bậc r hoặc r

-

chính qui. Có tầm quan trọng đặc biệt là các đồ thị bậc 3
(cubic graph), tức các đồ thị đều (chính qui) bậc 3. Một ví dụ điển hình về đồ thị
bậc 3 là đồ thị Petersen (Petersen graph), đồ thị này được vẽ ở Hình 1.19. Chú ý
rằng đồ thị rỗng N
n
là đồ thị chính qui bậc 0, đồ thị vòng C
n
là đồ thị chính qui bậc
2 và đồ thị đầy đủ K
n
là đồ thị chính qui bậc n


đồ thị hai phần có r đỉnh đen và s đỉnh trắng là K
r,s
. Các đồ thị K
1,3
; K
2,3
, K
3,3
và K
4,3
được vẽ ở Hình 1.22. Dễ dàng kiểm tra lại rằng K
r, s
có (r

+

s) đỉnh và r×s cạnh.

Hình 1.21. Đồ thị hai phần Hình 1.22. Đồ thị hai phần đầy đủ: K
1,3
, K
2,3
, K
3,3
, K
4,3


3
là đồ thị
hai phần đều, bậc 3 (Hình 1.23). Có thể kiểm tra lại rằng Q
k
có 2
k
đỉnh và k×2
k - 1
cạnh, và là đồ thị k

-

chính qui (đồ thị đều, bậc k).
Hình 1.23. Đồ thị hai phần đều, bậc 3: Q
3
Hình 1.24. Phần bù của đơn đồ thị G
1.2.9. Phần bù của đơn đồ thị
Nếu G là một đơn đồ thị với tập đỉnh V(G), thì phần bù (complement)
G
của
G là một đơn đồ thị, với cùng tập đỉnh V(G) và hai đỉnh kề nhau trong
G
khi và
chỉ khi chúng không kề nhau trong G. Chẳng hạn, Hình 1.24 vẽ đồ thị G và phần bù
G
của nó. Có thể thấy rằng phần bù của một đồ thị đầy đủ là một đồ thị rỗng và
phần bù của một đồ thị hai phần đầy đủ là hợp của hai đồ thị đầy đủ.

5
hay K
3,3
(Định lý Kuratowski).
Ví dụ. Hình lập phương vẽ ở Hình 1.25a là một đồ thị phẳng. Biểu diễn phẳng
của đồ thị được vẽ ở Hình 1.25b. Đồ thị này có số đỉnh n = 8, số cạnh m = 12 và số
diện d = 6 (5 diện hữu hạn và 1 diện vô hạn). Công thức Ơle đương nhiên đúng đối
với đồ thị phẳng này (8 - 12 + 6 = 2).
   
 
 
   
 
 
Hình 1.25. a) Hình lập phương; b) Biểu diễn phẳng
Tóm lại, chương này đã đề cập tới các khái niệm cơ bản về đồ thị: đỉnh, cạnh,
bậc của đỉnh, đồ thị vô hướng và đồ thị có hướng, đường đi và chu trình, đồ thị liên
thông và không liên thông. Trình bày các phép toán thường dùng trên đồ thị (thêm,
bớt đỉnh hoặc cạnh). Miêu tả nhiều dạng đồ thị đặc biệt: rừng và cây, đồ thị hình
sao, đồ thị vòng, đồ thị bánh xe, đồ thị đầy đủ, đồ thị hai phần, đồ thị hai phần đầy
đủ, đồ thị đều (chính qui), đồ thị Petersen, đồ thị Platon, đồ thị phẳng,
15

Chương 2
BÀI TOÁN TÔ MÀU ĐỒ THỊ

Chương này đề cập tới bài toán tô màu đồ thị và giới thiệu định lý bốn màu
nổi tiếng. Mục 2.1 xét bài toán tô màu các đỉnh của đồ thị. Mục 2.2 xét bài toán tô
màu bản đồ. Mục 2.3 xét bài toán tô màu các cạnh của đồ thị. Cuối chương, ở mục
2.4, đề cập tới đa thức màu và vấn đề có bao nhiêu cách tô màu có thể. Nội dung


Hình 2.1. Sắc số của đồ thị: (G) = 4
16
Chẳng hạn, đồ thị G vẽ ở Hình 2.1 có (G) = 4. Các màu được biểu thị bằng
chữ cái Hy lạp ( , , và ). Vì vậy, G là k

-

sắc tính với mọi k ≥ 4.
Vấn đề tìm số sắc tính của một đồ thị thường rất phức tạp (trừ khi G không có
chu trình), và cho tới nay nó vẫn chưa có một lời giải thỏa đáng. Trong mục này sẽ
trình bày một số kết quả đáng chú ý về các đồ thị k

-

sắc tính.
Sau đây ta giả thiết G là đơn đồ thị vô hướng, liên thông và không có khuyên.
Rõ ràng, sắc số của đồ thị đầy đủ n đỉnh bằng n: χ(K
n
) = n. Vì vậy có các đồ
thị với sắc số lớn tùy ý. Theo chiều ngược lại, χ(G) = 1 khi và chỉ khi G là đồ thị
không (null graph), tức là đồ thị G có đỉnh nhưng không có cạnh, và χ(G) = 2 khi
và chỉ khi G là một đồ thị hai phần khác không (non-null bipartite graph). Chú ý
rằng một cây bất kỳ, cũng như mọi chu trình độ dài chẵn bất kỳ là 2

-

sắc tính.
Ta có thể dễ dàng lấy ví dụ về đồ thị là 3 – sắc tính. Chẳng hạn, các chu trình
độ dài lẻ hay các đồ thị bánh xe với một số lẻ đỉnh và đồ thị Petersen là 3

(đồ thị đầy đủ r
đỉnh) như một đồ thị con thì sắc số của nó không ít hơn r. Nhìn chung, các kết quả
này không giúp ta biết chính xác sắc số của một đồ thị. Tuy nhiên, nếu biết bậc của
các đỉnh trong đồ thị thì ta có thể biết nhiều hơn.
Định lý 2.1. Nếu đơn đồ thị G có bậc lớn nhất của đỉnh bằng Δ thì G là (Δ

+

1)

-

sắc tính.
17
Chứng minh. Dùng phương pháp quy nạp toán học theo số đỉnh của G. Giả
sử G là một đơn đồ thị n đỉnh. Nếu ta xoá một đỉnh bất kỳ v, cùng với các cạnh liên
thuộc nó, thì đồ thị còn lại là một đơn đồ thị (n

-

1) đỉnh và bậc lớn nhất của đỉnh
cùng lắm bằng Δ (xem Hình 2.3). Theo giả thuyết quy nạp, đồ thị này là (Δ

+

1)

-

sắc tính. Giữ nguyên màu của các đỉnh trong đồ thị này, ta sẽ tô cho đỉnh v một

sắc
tính, và theo Định lý 2.2, mỗi đồ thị lập phương liên thông, khác đồ thị đầy đủ K
4
,
là 3

-

sắc tính. Mặt khác, nếu đồ thị có vài đỉnh với bậc lớn thì các định lý này cho
ta rất ít thông tin. Điều này được minh hoạ rõ bởi đồ thị hai phần đầy đủ K
1,s
. Định
lý Brooks cho thấy đồ thị này là s

-

sắc tính, nhưng thực tế chỉ cần dùng 2 màu là có
thể tô đúng các đỉnh của đồ thị loại này, nghĩa là K
1,s
là 2

-

sắc tính với mọi s.
Không có cách nào hiệu quả để thoát khỏi tình trạng này.
Tình trạng tồi tệ này sẽ không xảy ra, nếu ta giới hạn chỉ xét các đồ thị phẳng.
Trên thực tế, có thể dễ dàng chứng minh kết quả khá mạnh nói rằng mọi đơn đồ thị
phẳng là 6

-


-

sắc tính. ∎

Hình 2.4. Minh họa chứng minh Định lý 2.3
Cũng như Định lý 2.1, có thể làm mạnh thêm Định lý 2.3 này bằng cách xử lý
tinh tế hơn. Kết quả nhận được gọi là Định lý 5

màu (Five Colour Theorem).
Định lý 2.4. Một đơn đồ thị phẳng bao giờ cũng là 5

-

sắc tính.
Chứng minh. Tương tự như định lý 2.3, tuy nhiên các chi tiết sẽ phức tạp hơn.
Ta chứng minh định lý bằng phương pháp quy nạp theo số đỉnh. Hiển nhiên định lý
đúng đối với đơn đồ thị phẳng ít hơn 6 đỉnh. Giả sử G là một đơn đồ thị phẳng n
đỉnh, và mọi đơn đồ thị phẳng n

-

1 đỉnh là 5

-

sắc tính. Do đồ thị G phẳng nên G

(chẳng hạn, v
1
và v
3
) không kề nhau.
Bây giờ ta co hai cạnh vv
1
và vv
3
về đỉnh v, và nhận được một đồ thị phẳng có
n - 2 đỉnh. Theo giả thiết qui nạp, ta có thể tô đúng nó bằng 5 màu. Sau khi tô đồ thị
này, ta khôi phục trở lại hai cạnh ban đầu và tô cho v
1
và v
3
. bằng màu đã tô cho v,
còn v thì tô bằng màu thứ 5 còn lại (ngoài những màu đã tô cho các đỉnh kề v). Kết
quả là bao giờ ta cũng có thể tô cho các đỉnh của G bằng 5 màu, nghĩa là G là 5

-

sắc tính.

∎
Một câu hỏi tự nhiên đặt ra là liệu có thể làm mạnh hơn nữa định lý này được
không. Điều này dẫn đến một trong những bài toán nổi tiếng nhất trong toán học,
tồn tại hơn một thế kỷ, đó là bài toán bốn màu (Four-Colour Problem). Theo một
cách diễn đạt khác, bài toán này đã được đặt ra lần đầu tiên vào năm 1852, và cuối
cùng được K. Appel và W. Haken giải quyết năm 1976.



Để trả lời câu hỏi này, ta vẽ một đồ thị 5 đỉnh, mỗi đỉnh đại diện cho một loại
hóa chất, hai đỉnh là kề nhau khi các hóa chất tương ứng cần để xa nhau (xem Hình
2.6). Tô màu cho các đỉnh bằng các chữ cái Hy Lạp ( , , , ). Khi đó số màu sẽ
tương ứng với số nơi cần để hóa chất. Với ví dụ này do cần ít nhất 4 màu để tô, nên
cần 4 nơi khác nhau để hóa chất trong kho. Chẳng hạn, hóa chất a và e có thể để ở
nơi có màu α, các hóa chất b, c và d để ở nơi có màu tương ứng là β, γ và δ.
Ta kết thúc vấn đề tô màu các đỉnh bằng Định lý Minty nêu một tính chất đặc
trưng của đồ thị k

-

sắc tính. Trong đồ thị G cho trước, ta chọn một hướng tùy ý trên
mỗi cạnh. Nếu là một chu trình thì ta gọi t
1
( ) là số cạnh hướng theo cùng một
chiều của , t
2
( ) là số cạnh hướng theo chiều ngược lại, và giả thiêt t
1
( ) ≥ t
2
( ).
Định lý 2.6. (G. J. Minty, 1962) Một đồ thị là k

-

sắc tính khi và chỉ khi có thể
chọn hướng trên mỗi cạnh của nó sao cho trên mọi chu trình sơ cấp (chu trình
không đi qua đỉnh nào hai lần trở lên) đều có t

thể dễ dàng bị loại bỏ (xem Hình 2.9). Để bao quát được các trường hợp này và các
trường hợp tương tự, ta quan niệm bản đồ là một đồ thị phẳng 3

-

liên thông, nghĩa
là phải bỏ đi ít nhất 3 đỉnh mới có thể làm đồ thị mất liên thông. Như vậy bản đồ
không có "tập cắt" (tập cạnh bó đi thì đồ thị sẽ mất liên thông) gồm 1 hoặc 2 cạnh,
và nói riêng không có đỉnh bậc 1 hoặc 2. Vì vậy như ta sẽ thấy, việc loại bỏ cầu nối
ở đây tương ứng với việc loại bỏ các khuyên (cạnh nối một đỉnh với chính nó).
Ta nói một bản đồ là k

-

sắc tính diện nếu có thể tô các nước (diện) bằng k
màu sao cho hai nước có đường biên giới (cạnh) chung được tô bằng hai màu khác
nhau. Để tránh nhầm lẫn, ta dùng k

-

sắc tính đỉnh để chỉ k

-

sắc tính theo nghĩa tô
các đỉnh. Chẳng hạn, bản đồ ở Hình 2.10 là 3

-

sắc tính diện và 4

⇐ Nếu mọi đỉnh của G có bậc chẵn thì ta sẽ tô các diện của G bằng 2 màu như
sau: Chọn diện bất kỳ F và tô nó bằng màu đỏ. Vẽ một đường cong từ điểm x trong
F tới điểm y trong diện khác F' và không đi qua đỉnh nào của G. Nếu đường cong
đó đi qua một số chẵn cạnh thì tô màu đỏ cho diện chứa y. Nếu trái lại, tô màu xanh.
(xem Hình 2.11). Việc tô màu này được hoàn toàn xác định, vì có thể lấy một chu
trình gồm hai đường như thế và chứng minh rằng chu trình đi qua một số chẵn cạnh
của G, nhờ dựa trên sự kiện là mỗi đỉnh có một số chẵn cạnh liên thuộc nó. ∎
Một chứng minh đơn giản hơn của Định lý 2.7 dựa trên việc chuyển về bài
toán tô màu các đỉnh của đồ thị đối ngẫu. Cho đồ thị phẳng G, đồ thị đối ngẫu (dual
graph) G* của G được xây dựng như sau: trong mỗi diện f của G, chọn một điểm
v*, các điểm này là các đỉnh của G*; với mỗi cạnh e của G, ta vẽ một cạnh e*, cắt e
(không cắt các cạnh khác của G) và nối hai đỉnh thuộc hai diện có chung cạnh e,
các cạnh như thế tạo nên tập cạnh của G* (xem Hình 2.12),
Định lý 2.8. Cho G là một đồ thị phẳng, không có khuyên và G* là đồ thị đối
ngẫu của G. Khi đó, G là k

-

sắc tính đỉnh khi và chỉ khi G* là k

-

sắc tính diện.
Chứng minh. ⇒ Ta có thể giả thiết G là một đơn đồ thị liên thông, do đó G*
là một bản đồ. Nếu G là k

-

sắc tính đỉnh thì ta có thể dùng k màu để tô các diện của
G* sao cho mỗi diện thừa hưởng màu của đỉnh duy nhất nằm trong diện đó (xem


sắc tính khi và chỉ khi mọi đỉnh của G có bậc
chẵn.
Chứng minh thứ hai. Có thể chỉ ra rằng đối ngẫu của đồ thị phẳng mà mọi
đỉnh có bậc chẵn là một đồ thị phẳng hai phần và ngược lại. Vì vậy ta chỉ cần để ý
rằng một đồ thị phẳng, liên thông và không có khuyên là 2

-

sắc tính đỉnh khi và chỉ
khi nó là một đồ thị hai phần. ∎
Tương tự, ta có thể chứng minh hai dạng của định lý bốn màu là tương đương.
Hệ quả 2.1. Định lý bốn màu đối với các bản đồ tương đương với định lý bốn
màu đối với các đồ thị phẳng.
Chứng minh. ⇒ Ta có thể giả thiêt G là một đơn đồ thị phẳng liên thông. Khi
đó, đồ thị đối ngẫu G* là một bản đồ. Theo Định lý 2.8, nếu G* là 4-sắc tính diện
thì G là 4

-

sắc tính đỉnh.
⇐ Ngược lại, giả sử G là một bản đồ và G* là đồ thị đối ngẫu của G. Khi đó,
G* là một đơn đồ thị phẳng và vì vậy theo định lý 2.8, nếu G* là 4

-

sắc tính đỉnh
thì G là 4

-