Header Page 1 of 89.

ĐẠ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

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

Thái Nguyên - 2015
Footer Page 1 of 89.


Header Page 2 of 89.

ĐẠ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
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

Nội dung luận văn được viết trong hai chương.

Footer Page 3 of 89.

1


Header Page 4 of 89.

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à
tạo mọi điều kiện thuận lợi trong quá trình tác giả học tập và nghiên cứu.



Đồ thị (graph) là một tập hợp hữu hạn và khác rỗng các điểm, gọi là các đỉnh
(vertex) hay nút (node), và một tập hợp các đường (thẳng hay cong) nối liền một số
cặp điểm này, gọi là các cạnh (edge) của đồ thị (Số cạnh có thể bằng 0).
Mỗi đỉnh của đồ thị thường được ký hiệu bằng một chữ cái (a, b, c, ... hay A,
B, C, ...) hoặc chữ số (1, 2, 3, ...). Cạnh nối liền đỉnh v với đỉnh w được ký hiệu là
(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.

Footer Page 5 of 89.

3


Header Page 6 of 89.

Để 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ị.



(v) và

-

(v).

Qui ước: khuyên tại một đỉnh được tính 2 lần. Ví dụ trong đồ thị vẽ ở Hình 1.7 ta
có (P) = (S) = (U) = (V) = 2; (Q) = (R) = 3 và (T) = 4 (có khuyên ở T).
Dễ dàng chứng minh các tính chất sau đây về bậc của đỉnh trong đồ thị:
a) Trong một đồ thị vô hướng, tổng số bậc của mọi đỉnh bằng hai lần số cạnh
của đồ thị và số đỉnh có bậc lẻ bao giờ cũng là một số chẵn.
b) Trong một đồ thị có hướng, tổng các bậc vào của mọi đỉnh bằng tổng các
bậc ra của mọi đỉnh và bằng tổng số cung trong đồ thị.
Nhiều tính chất của đồ thị có hướng không phụ thuộc vào hướng các cung
trong đồ thị. Vì thế, khi bỏ qua hướng trên các cung (đổi cung thành cạnh) ta sẽ
nhận được một đồ thị vô hướng, gọi là đồ thị nền của đồ thị có hướng đã cho.
1.1.2. Phép toán trên đồ thị
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).


Hình 1.9. Các đồ thị đẳng cấu với đồ thị ở Hình 1.3

1.1.4. Đồ thị liên thông
Có thể ghép hai đồ thị để lập lên một đồ thị lớn hơn. Cho G1 = (V(G1), E(G1)),
G2 = (V(G2), E(G2)) với V(G1) ∩V(G2) = ∅. Khi đó, hợp (union) G1 ∪ G2 là đồ thị
có tập đỉnh là V(G1) ∪ V(G2) và tập cạnh là E(G1) ∪ E(G2) (Hình 1.10).

Hình 1.10. Đồ thị G1, G2 và hợp G1 ∪ G2

Hình 1.11. Đồ thị không liên thông

Hầu hết các đồ thị thường gặp là đồ thị ghép. Một đồ thị được gọi là liên thông
(connected graph) nếu nó không biểu diễn được dưới dạng hợp của hai hay nhiều

Footer Page 8 of 89.

6


Header Page 9 of 89.

đồ thị. Trái lại, đồ thị gọi là không liên thông (disconnected graph). Rõ ràng là bất
cứ một đồ thị không liên thông G nào cũng biểu diễn được dưới dạng hợp của các
đồ thị liên thông, mỗi đồ thị liên thông gọi là một thành phần liên thông của G.
Chẳng hạn, một đồ thị gồm ba thành phần liên thông được vẽ ở Hình 1.11.

Hình 1.12. Các kiểu đồ thị liên thông không quá 5 đỉnh

Footer Page 9 of 89.

một đồ thị cỡ lớn trên máy tính. Có cách lưu giữ một đơn đồ thị là liệt kê các đỉnh
kề với mỗi đỉnh của đồ thị. Ví dụ cho cách biểu diễn này được chỉ ra ở Hình 1.13.
v
u

w

u : v, y
v : u, w, y
w: v, x, y
x w, y
y : u, v, w, x

x
y
Hình 1.13. Liệt kê các đỉnh kề

∙

∙

∙

∙

Hình 1.14. Đồ thị rỗng N4

Một cách biểu diễn hữu ích khác là dùng các ma trận.

Footer Page 10 of 89.


Footer Page 11 of 89.

9


Header Page 12 of 89.

đỉnh) thì đồ thị còn lại sẽ tăng thêm một thành phần liên thông, mỗi thành phần
gồm ít nhất một cạnh. Ví dụ, các đồ thị vẽ ở Hình 1.9 là liên thông, còn đồ thị vẽ ở
Hình 1.11 là không liên thông (gồm 3 thành phần liên thông).
Một đồ thị vô hướng không có chu trình gọi là một rừng (forest). Một rừng
liên thông gọi là một cây (tree), tức cây là một đồ thị liên thông và không có chu
trình. Ví dụ phả hệ của một họ tộc là một cây (cây phả hệ). Rừng có thể gồm nhiều
thành phần liên thông khác nhau, mỗi thành phần liên thông là một cây. Như vậy,
rừng gồm nhiều cây. Đỉnh có bậc 1 trong cây gọi là một lá (leaf). Đồ thị hình sao là
một cây có duy nhất một đỉnh không phải là lá.
Một đồ thị con, không chứa chu trình của đồ thị G gọi là một cây của G. Một
đồ thị con bao trùm của G mà là một cây được gọi là một cây bao chùm (spanning
tree) của G. Một số tính chất đặc trưng của cây: cây n đỉnh có đúng n - 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à Kn. Số cạnh của Kn
bằng n(n - 1)/2. Đồ thị K4 và K5 được vẽ ở Hình 1.17.


1.2.6. Đồ thị Platon
Trong các đồ thị chính qui, đáng chú ý là các đồ thị Platon (Platonic graph).
Đồ thị Platon được hình thành từ các đỉnh và các cạnh của 5 khối đa diện đều: hình

Footer Page 13 of 89.

11


Header Page 14 of 89.

tứ diện, hình tám mặt, hình lập phương, khối hai mươi mặt và khối mười hai mặt
(Hình 1.20).

Tứ diện

Hình tám mặt Hình lập phương Khối 20 mặt

Khối 12 mặt

Hình 1.20. Đồ thị Platon

1.2.7. Đồ thị hai phần
Nếu tập đỉnh của đồ thị G có thể chia tách ra thành hai tập rời nhau A và B sao
cho mỗi cạnh của G nối một đỉnh thuộc A với một đỉnh thuộc B, thì G được gọi là
một đồ thị hai phần (bipartite graph) (Hình 1.21). Nói một cách khác, đồ thị hai
phần là đồ thị mà có thể tô các đỉnh của nó bằng hai màu đen và trắng sao cho mỗi
cạnh nối một đỉnh đen (trong A) và một đỉnh trắng (trong B).
Có thể chứng minh rằng đơn đồ thị G là đồ thị hai phần khi và chỉ khi mọi chu
trình trong G đều có độ dài (số cạnh) chẵn.

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 đủ.
1.2.10. Đồ thị phẳng
Một đồ thị (hay đa đồ thị) G gọi là đồ thị phẳng (planar graph) khi nào nó có
thể biểu diễn được trên một mặt phẳng sao cho ứng với mỗi đỉnh là một điểm và
ứng với mỗi cạnh là một đoạn thẳng hay cong và bất kỳ hai cạnh nào cũng không
có điểm chung khác với các đầu mút của chúng. Chẳng hạn, đồ thị vẽ ở Hình 1.4 và
Hịnh 1.5 là các (đa) đồ thị phẳng.
Khi đó, mỗi miền mặt phẳng hạn định bởi các cạnh và không chứa đỉnh hoặc
cạnh ở bên trong của nó, gọi là một diện (face) của đồ thị phẳng G. Biên (boundary)
của một diện là chu trình tạo nên bởi các cạnh hạn định nó. Hai diện gọi là kề nhau

Footer Page 15 of 89.

13


Header Page 16 of 89.

(adjacent) khi nào biên của chúng có ít nhất một cạnh chung (hai diện chỉ có đỉnh
chung thì không xem là kề). Rõ ràng mỗi đồ thị phẳng liên thông đều có một diện
vô hạn duy nhất, còn mọi diện khác đều là diện hữu hạn.
Ví dụ. Một bản đồ địa lý không có đảo (không có khuyên) là một đồ thị 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, ...

Footer Page 16 of 89.

14


Header Page 17 of 89.

Chương 2

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: χ(Kn) = 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 - sắc tính.
Các đồ thị bánh xe với một số chẵn đỉnh là 4 - sắc tính. Trong [1] đưa ra một lớp đồ
thị phẳng 3 - sắc tính đáng chú ý, đó là các đồ thị với n ≥ 6 đỉnh và mọi đỉnh có bậc
3 (Hình 2.2).

Hình 2.2. Đồ thị phẳng đẳng cấp bậc 3 là 3 - sắc tính

Ta có thể nói đôi điều về số sắc tính (sắc số) của một đồ thị tuỳ ý: Nếu đồ thị
có n đỉnh thì sắc số của nó không vượt quá n, và nếu đồ thị chứa Kr (đồ 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.

Footer Page 18 of 89.

16

thể tô đúng các đỉnh của đồ thị loại này, nghĩa là K1,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.
Định lý 2.3. Mọi đơn đồ thị phẳng là 6 - sắc tính.

Footer Page 19 of 89.

17


Header Page 20 of 89.

Chứng minh. (Tương tự như Định lý 2.1, tức là dùng phương pháp quy nạp
theo số đỉnh của đồ thị) Hiển nhiên định lý đúng đối với các đơn đồ thị phẳng
không quá 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à 6 - sắc tính. Do đồ thị G phẳng nên G chứa một đỉnh v có bậc
nhiều nhất là 5. Nếu xoá v và các cạnh liên thuộc v thì đồ thị còn lại có n - 1 đỉnh,
và vì vậy nó là 6 -sắc tính (xem Hình 2.4). Giữ nguyên màu của các đỉnh trong đồ
thị này, ta tô cho đỉnh v bằng màu, khác với những màu đã tô cho các đỉnh kề v (số
này không quá 5). Kết quả là G được tô bằng 6 màu, tức G 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.

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.

Hình 2.5. Minh họa Định lý 2.4

Hình 2.6. Tìm nơi để hóa chất a - e

Định lý 2.5. (Appel và Haken, 1976) Mọi đơn đồ thị phẳng là 4 - sắc tính.
Chúng minh định lý này được thực hiện trong một số năm và tiêu tốn nhiều
thời gian chạy máy tính, suy cho cùng nó dựa trên việc mở rộng phức tạp các ý
tưởng trong chứng minh định lý 5 - màu.
Ứng dụng thực tế. Ta nêu một ứng dụng đơn giản của việc tô màu đỉnh. Giả
sử một nhà hóa học muốn cất giữ 5 loại hóa chất a, b, c, d và e trong kho. Một số
hóa chất có tương tác mạnh khi tiếp xúc, vì thể chúng cần được để cách xa nhau

Footer Page 21 of 89.

19


Header Page 22 of 89.

trong kho. Dấu * trong bảng sau cho biết những cặp hóa chất không được để gần
nhau. Cần bao nhiêu nơi trong kho để cất giữ hóa chất?

Để 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

20


Header Page 23 of 89.

Hình 2.7. Bản đồ tô bằng 4 màu

Hình 2.8. Cầu trong bản đồ

Hình 2.9. Đỉnh bậc 2

Để chính xác hóa mệnh đề này, ta cần giải thích rõ thế nào là một bản đồ. Do
hai màu ở mỗi phía của một cạnh phải khác nhau, nên ta cần loại trừ những bản đồ
có chứa cầu nối (xem Hình 2.8). Ta cũng cần loại trừ các đỉnh bậc 2, vì chúng có
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 - sắc tính đỉnh.

Hình 2.10. Tô đỉnh và tô diện

Hình 2.11. Minh họa Định lý 2.7

Định lý bốn màu đối với bản đồ nói rằng mọi bản đồ là 4 - sắc tính diện. Hệ

Đị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
Hình 2.12). Hai diện kề nhau trong G* có màu khác nhau, bởi vì các đỉnh của G
nằm trong hai diện này là kề nhau trong G, nên chúng có màu khác nhau. Vì vậy
G* là k- sắc tính diện.

Hình 2.12. Đồ thị đối ngẫu G*: tô đỉnh của G tương đương tô diện của G*

Footer Page 24 of 89.

22


Header Page 25 of 89.

⇐ Bây giờ giả sử rằng G* là k - sắc tính diện. Khi đó dùng k màu ta có thể tô
các đỉnh của G sao cho mỗi đỉnh thừa hưởng màu của diện chứa nó. Bằng lập luận
tương tự như trên có thể thấy rằng không có hai đỉnh kề nhau nào trong G lại có
màu như nhau. Vì vậy G là k - sắc tính đỉnh.

∎

Từ đó suy ra có thể phát biểu dạng đối ngẫu cho định lý bất kỳ về tô đỉnh của
một đồ thị phẳng để đưa ra định lý về tô diện của bản đồ và ngược lại. Để làm ví dụ,
ta trở lại Định lý 2.7 và xét cách chứng minh khác của định lý này. Ta nhắc lại
Định lý 2.7. Bản đồ G là 2 - sắc tính khi và chỉ khi mọi đỉnh của G có bậc
chẵn.