Lý thuyết đồ thị qua các định lý và bài toán
1. Mở đầu, định nghĩa và khái niệm
1. Đồ thị là cặp các tập hợp G = (V,E) trong đó V là tập các đỉnh, còn E là họ các cạnh có
đầu mút thuộc vào V. Đồ thị có thể có vô số đỉnh và vô số cạnh. Dưới đây, nếu không nói
gì thêm, ta sẽ giả sử các đồ thị là đơn, tức là không có khuyên và cạnh song song.
2. Hai đỉnh v, w được gọi là kề nhau nếu có cạnh nối v và w. Một cạnh và một đỉnh được
gọi kề nhau (incident) nếu đỉnh là đầu mút của cạnh.
3. Cho một đỉnh v, bậc của đỉnh v theo định nghĩa là số cạnh nhận v là một trong hai đầu
mút.
4. Một đường đi trong đồ thị G được định nghĩa là dãy hữu hạn các đỉnh khác nhau v
0
, v
1
,
, v
t
sao cho v
i
kề với v
i+1
. Độ dài của đường đi là số cạnh có trong đường đi đó.
5. Một chu trình của đồ thị G theo định nghĩa là một dãy các đỉnh khác nhau v
0
, v
1
, , v
t
sao cho v
i
kề với v
i+1

hợp. Đồ thị k phe đầy đủ được định nghĩa như đồ thị hai phe đầy đủ. Trong trường hợp |
A
i
| = n
i
, đồ thị như thế được ký hiệu là K
n1
,
n2
, ,
nk
.
13. Một cạnh mà hai đầu mút trùng nhau gọi là khuyên. Đồ thị mà trong đó có hơn một
cạnh nối cặp hai đỉnh được (cạnh song song) gọi là đa đồ thị. Một đồ thị không khuyên
và không có cạnh song song gọi là đồ thị đơn.
Bài tập phần 1.
Các bài tập phần này sẽ giúp các bạn làm quen với các kỹ thuật cần dùng đến khi giải các bài toán
olympic. Bạn rất cần biết cách giải tất cả các bài toán này.
1. Cho G là một đồ thị có n đỉnh và m cạnh và bậc của n đỉnh là d1, d2, , dn. Chứng
minh rằng
d
1
+ d
2
+ + d
n
= 2m.
2. Với mọi đồ thị G, gọi ∆(G) là bậc lớn nhất giữa các đỉnh của G. Hãy mô tả tất cả các
đồ thị với ∆(G) ≤ 2. Hãy mô tả tất cả các đồ thị với ∆(G) = 2.
3. Giả sử G là đồ thị không liên thông. Chứng minh rằng đồ thị bù G' của G liên thông.

iii) Hai máy tính và sợi dây nối chúng được tô màu khác nhau.
11. Cho đồ thị G, gọi χ(G) là số màu ít nhất cần dùng để tô màu các đỉnh của G sao cho
không có hai đỉnh kề nhau được tô cùng màu. Gọi m là số cạnh trong G. Chứng minh
rằng
4
1
2
2
1
)( ++≤ mG
χ
.
12. Gọi G là một đồ thị có 9 đỉnh. Giả sử rằng với 5 điểm bất kỳ của G, luôn tồn tại ít
nhất 2 cạnh mà các đầu mút nằm trong đỉnh đó. Tìm số bé nhất các cạnh của G.
2. Cây và cân bằng
Cây được định nghĩa là đồ thị liên thông không có chu trình. Trước hết ta đưa ra các đặ
trưng của các đồ thị như vậy.
Bổ đề: (Đặc trưng của cây) Cho G là một đồ thị liên thông có n đỉnh. Khi đó các điều sau
đây là tương đương.
1. G không chứa chu trình.
2. G có đúng n - 1 cạnh.
3. Với hai đỉnh bất kỳ, tồn tại duy nhất một đường đi nối hai đỉnh đó.
4. Bỏ đi một cạnh bất kỳ thì tính liên thông bị mất.
Hệ quả: Giả sử G là một đồ thị liên thông với n đỉnh và ít nhất n cạnh. Khi đó tồn tại ít
nhất một đỉnh mà bỏ đỉnh này đi đồ thị vẫn còn liên thông (nói cách khác, tồn tại một
cạnh không là cầu).
Hệ quả: Cho G là đồ thị liên thông. Khi đó G chứa một đồ thị con là cây và chứa mọi
đỉnh của G. Đồ thị như vậy gọi là cây bao trùm của G.
Cho G là một cây và v là một đỉnh bất kỳ của G. Gọi v
1

cho
)1(
1
)()1(
1
−
∆
−∆
≤≤−
∆
nvfn
Sketch of Proof: Left inequality follows for all v from pigeonhole principle. To prove the
right inequality, choose v such that f (v) is minimum. Suppose f (v) ≥ (∆ − 1)/(∆).(n − 1)
+ 1. Let v
i
be the neighbour of v with |T
i
| ≥ (∆ −1)/∆(n −1)+1. Let v = w
1
, w
2
, , w
∆
be
the neighbours of v
i
. Then since the tree containing v after removing v
i
v contains at most
1/∆(n − 1) vertices, then f (vi) ≤ (∆ − 1)/∆(n − 1) − 1 < f (v), contradicting the minimality

người ngoài S quen với tất cả mọi người trong S. Chứng minh rằng có một người quen
với tất cả người khác.
3. Định lý Turan: Cho G là đồ thị n đỉnh và m là số nguyên dương với 2 ≤ m ≤ n. Giả sử
rằng G không chứa băng nhóm kích thước m. Chứng minh rằng số cạnh của G không
vượt quá






−
−
1
1
1
2
2
m
n
.
4. (APMO 1990) Một nhóm n người dự tiệc có tính chất là mỗi một cặp hai người thì
hoặc quen nhau, hoặc không quen nhau. Các điều kiện sau đây cũng được thỏa mãn.
• Không có ai quen với tất cả mọi người.
• Hai người không quen nhau bất kỳ có đúng một người quen chung.
• Không có ba người đôi một quen nhau.
Chứng minh rằng mỗi người có số người quen bằng nhau.
Các bài toán Olympic
1. Cho n là số nguyên dương. Với tập S gồm 2n số thực, hãy tìm số lớn nhất có thể các
hiệu (dương) đôi một khác nhau giữa hai phần tử của S nằm trong khoảng (1, 2).

viên của một băng được gọi là kích thước của băng đó. Biết rằng, trong cuộc thi này,
kích thước lớn nhất của một băng là chẵn. Chứng minh rằng ta có thể sắp các thí sinh vào
2 phòng sao cho kích thước lớn nhất của một băng trong một phòng cũng bằng kích
thước lớn nhất của một băng trong phòng còn lại.
(Gợi ý: Hãy làm theo sơ đồ chuẩn mực sau. Gọi C là băng có kích thước lớn nhất. Xếp tất
cả mọi người vào một phòng, sau đó bắt đầu xếp những người trong C từng người một
vào phòng kia cho đến khi hiệu của kích thước băng lớn nhất ở hai phòng bằng 0 hoặc
bằng 1. Nếu trường hợp thứ nhất xảy ra thì xong. Còn nếu trường hợp thứ hai thì sao?)
4. Đồ thị có hướng. Mũi tên và Giải đấu.
Đồ thị có hướng là đồ thị mà mỗi cạnh được định hướng bằng một mũi tên chỉ theo đúng
một hướng. Đường đi có hướng là đường đi đi theo chiều của các mũi tên. Chu trình có
hướng được định nghĩa tương tự. Giải đấu theo định nghĩa là đồ thị có hướng đầy đủ.
Các bài toán khởi động
1. Chứng minh rằng mọi giải đấu đều có đường đi có hướng đi qua tất cả các đỉnh. Giả sử
rằng với mọi cặp đỉnh, tồn tại đường đi có hướng từ đỉnh này đến đỉnh kia. Ta gọi đồ thị
như vậy là liên thông mạnh. Chứng minh rằng một giải đấu có chu trình có hướng đi qua
tất cả các đỉnh khi và chỉ khi nó liên thông mạnh.
2. Cho G là một đồ thị liên thông có số cạnh chẵn. Chứng minh rằng ta có thể đánh dấu
các cạnh bằng các mũi tên sao cho số các mũi tên ra từ mỗi đỉnh là chẵn.
Các bài toán olympic
1. (Canada 2006) Xét giải đấu vòng tròn với 2n +1 đội, trong đó hai đội bất kỳ đấu với
nhau đúng một trận. Ta nói rằng ba đội X, Y, Z lập thành một bộ ba vòng tròn nếu X
thắng Y , Y thắng Z , Z thắng X. Ở đây không có hòa.
(a) Tìm GTNN của số bộ ba vòng tròn.
(b) Tìm GTLN của số bộ ba vòng tròn.
2. (Romania 2006) Mỗi một cạnh của đa diện được định hướng bởi một mũi tên sao cho
tại mỗi đỉnh có ít nhất một mũi tên đi và ít nhất một mũi tên đến. Chứng minh rằng tồn tại
một mặt của đa diện mà các cạnh biên của nó tạo thành một chu trình có hướng.
3. Cho k, n là các số nguyên dương với k < n sao cho
1

5. Tương thích: Hãy bắt cặp
Cho đồ thị G, một tương thích M là một tập hợp các cạnh thuộc G sao cho không có hai
cạnh thuộc M có đỉnh chung. Một tương thích được gọi là đầy đủ nếu mọi đỉnh thuộc G
đều kề với một cạnh nào đó của M. Một đỉnh được gọi là M-bỏ qua nếu nó không kề với
một cạnh thuộc M. Rõ ràng, M sẽ là tương thích đầy đủ nếu không có đỉnh M-bỏ qua. Ta
phát biểu hai tính hất quan trọng liên quan đến tương thích.
Định lý Hall: Cho G = A ∪ B, A ∩ B = ∅ là đồ thị hai phe. Với tập con S khác ∅ thuộc
A, gọi Γ(S) là tập các đỉnh trong B kề với đỉnh nào đó trong S. Khi đó tồn tại một tương
thích chứa tất cả các đỉnh thuộc A khi và chỉ khi với mọi S ⊆ A, |Γ(S)| ≥ |S|.
Điều kiện sau cùng được gọi là Điều kiện Hall. Trong trường hợp đặc biệt khi |A| = |B|,
thì G có tương thích đầy đủ khi và chỉ khi G thỏa mãn điều kiện Hall.
Sketch of Proof: Strong induction on |A|. If |A| = 1, clear. Suppose |A| = n. If for all S ⊆
A, |Γ(S)| ≥ |S| + 1, then choose e = uv ∈ E(G) with u ∈ A. Hall’s Condition still applies to
the graph G − {u, v}. Done. Otherwise, |Γ(S)| = S for some S ⊆ A. I claim Hall’s
condition holds for the graph induced by (A − S) ∪ (B − Γ(S)). For T ⊆ A − S, let Γ
0
(T )
be the neighbours of T in B − Γ(S). Then by Hall’s condition on all of G, Γ(S ∪ T ) ≥ S
∪ Γ
0
(T ). Since |Γ(S)| = |S|, then |T | ≥ |Γ
0
(T )|. Then strong induction applies.
Một mô hình nữa: Các bạn sẽ gặp các bài toán trong đó có bảng các số. Ví dụ bạn có một
bảng chữ nhật m × n trong đó ghi các số thuộc tập hợp {0, 1}. Hãy suy nghĩ xem ta có thể
xây dựng một cách tự nhiên đồ thị với hai phe, mỗi phe có m, n đỉnh tương ứng.
Các bài toán khởi động:
1. Cho n là số nguyên dương. Cho S
1
, S

không âm sao cho tổng các số trên mỗi hàng và trên mỗi cột bằng nhau. Chứng minh
rằng G có thể viết dưới dạng tổng của các bảng hoán vị. (Phép cộng các bảng được thực
hiện theo vị trí.)

3. (Iran 1998) Cho n ≥ 3 là số nguyên dương. Cho G là gồm các số 0, 1 hoặc −1 sao cho
trên mỗi một hàng và mỗi một cột có đúng một số 1 và một số −1. Chứng minh rằng các
hàng và các cột của bảng có được sắp xếp lại để kết quả là bảng -G.
4. Bảng n × n gồm các số thuộc {0, 1} sao cho với mọi tập con gồm n ô, trong đó không
có hai ô cùng hàng hoặc cùng cột, chứa ít nhất một số 1. Chứng minh rằng tồn tại i hàng
và j cột với i + j ≥ n + 1, có giao chứa toàn 1.
5. There are 2n people in a room where each pair of persons is classified as friends or
strangers. Two game players from the outside play a game where they alternate turns
picking one person in the room such that this person was not picked before and this
person is friends with the person previously picked. The last player who can make a legal
move wins. The player that moves first can pick anyone he/she wants. Prove that the
player that moves second has a winning strategy if and only if the 2n people can be used
to form n disjoint pairs such that the two people in each pair are friends.
6. Đường đi và chu trì Euler. Đường đi và chu trình Hamilton
Cho đồ thị G, một đường đi Euler là dãy liên tiếp các đỉnh kề nhau sao cho mỗi một cạnh
của đồ thị đều xuất hiện trong đường đi đó đúng một lần. Chu trình Euler là dãy các đỉnh
như vậy, nhưng khởi đầu và kết thúc ở cùng một đỉnh.
Đặc trưng của đường đi Euler và chu trình Euler: Một đồ thị liên thông có đường đi Euler
khi và chỉ khi số các đỉnh bậc lẻ của nó là 0 hoặc 2. Một đồ thị liên thông có chu trình
Euler khi và chỉ khi tất cả các đỉnh của nó đều có bậc chẵn.
Chứng minh: Bạn có thể tự chứng minh. Khá dễ.
Bây giờ ta quay trở lại với đồ thị đơn. Đường đi Hamilton là đường đi đi qua tất cả các
đỉnh của đồ thị, mỗi đỉnh đúng một lần. Chu trình Hamilton là chu trình đi qua tất cả các
đỉnh của đồ thị, mỗi đỉnh một lần. Đồ thị chứa chu trình Hamilton được gọi là chu trình
Hamilton. Nói chung là khó có thể xác định được trong một đồ thị đã cho có chu trình
Hamilton hay không. Có một kết quả hữu ích là định lý Dirac.

điểm nào thẳng hàng và không có 4 điểm nào cùng nằm trên một đường tròn. Gọi f(S) là
số cặp điểm (không có thứ tự) (P,Q) của S sao cho tồn tại đường tròn chứa P, Q bên
trong, nhưng không chứa điểm nào khác của S. Tìm giá trị lớn nhất có thể của. Viết đáp
số như một hàm số theo n.
4. (IMO 1991) Cho G là đồ thị liên thông có m cạnh. Chứng minh rằng các cạnh có thể
dán nhãn bằng các số nguyên dương 1, 2, , m sao cho với mỗi đỉnh có bậc ít nhất là 2,
ước số chung lớn nhất của tất cả các nhãn trên các cạnh kề với đỉnh này bằng 1.
5. (Belarus 2005) Chứng minh rằng không thể tô màu các ô của hình vuông 11 × 11 bằng
3 màu sao cho không có 4 hình vuông nào có tâm lập thành hình chữ nhật có cạnhsong
song với cạnh của hình vuông được tô cùng màu.
6. (St. Petersburg) Cho n ≥ 3, k ≥ 2 là các số nguyên dương. Có một nhóm n học sinh,
trong k ngày, mỗi ngày có một nhóm gồm ít nhất 2 học sinh đi mua kem, sao cho mỗi cặp
học sinh đi mua kem đúng một lần. Chứng minh rằng k ≥ n.
7. Cho n là số nguyên dương. Chứng minh rằng các cạnh của đồ thị đầy đủ n đỉnh có thể
phân ra thành n-1 đường đi có độ là 1, 2, , n-1.
8. (IMO 2005) Trong một cuộc thi toán có 6 bài toán. Hai bài toán bất kỳ trong số các bài
toán này cùng giải được bởi ít nhất 2/5 số thí sinh. Hơn nữa, không có học sinh nào giải
được cả 6 bài toán. Chứng minh rằng có ít nhất hai học sinh mà mỗi học sinh giải được
đúng 5 bài toán.
9. Chứng minh rằng trong một nhóm có 17 người, trong đó mỗi người có đúng 4 người
quen, tìm được 2 người không quen nhau và không có người quen chung.
10. Cho n điểm được nối bởi các đoạn thẳng sao cho mỗi một điểm đều được nối với ít
nhất một điểm khác và không có hai điểm nào có thể được nối bằng hai đường gấp khúc
khác nhau. Chứng minh rằng tổng số các cạnh bằng n-1.
11. Có một nhóm người, trong đó bất kỳ hai người nào quen nhau cũng không cùng quen
với một người khác và bất kỳ hai người nào không quen nhau cũng cùng quen với đúng
hai người khác. Chứng minh rằng trong nhóm đó, mọi người đều có số lượng người quen
bằng nhau.
12. Tại một hội nghị có 100 đại biểu. Trong số đó có 15 người Pháp, mỗi người quen với
ít nhất 70 đại biểu và 85 người Đức, mỗi người quen với không quá 10 đại biểu. Họ được

0
})| ≥ 1, do đó tồn tại y
0
thuộc Y kề với X. Ta đặt f(x
0
) = y
0
. Bây giờ
xét X’ = X \{x} và Y’ = Y \ {y}, A ⊂ X’ và G’(A) là tập các đỉnh thuộc Y’ kề với A. Khi
đó |G’(A)| ≥ |G(A)| - 1 ≥ |A|. Vì |X’| < |X| nên theo giả thiết quy nạp, tồn tại đơn ánh f: X’
 Y’ sao cho f(x) kề x với mọi x thuộc x’. Bổ sung thêm f(x
0
) = y
0
ta được đơn ánh f: X
 Y thỏa mãn yêu cầu định lý.
2) Trong trường hợp ngược lại, tồn tại A ⊂ X (A ≠ X) sao cho |G(A)| = |A|. Khi đó, do |A|
< |X| nên tồn tại đơn ánh f: A  G(A). Xét X’ = X \ A, Y’ = Y \ G(A). Xét B thuộc X’ và
G(B) là tập các đỉnh thuộc Y’ kề với B. Nếu |G(B)| < |B| thì ta có
|G(A ∪ B)| = |G(A)| + |G(B)| < |A| + |B| = |A ∪ B|
mâu thuẫn với điều kiện định lý. Như vậy ta có |G(B)| ≥ |B| với mọi B thuộc X’. Theo giả
thiết quy nạp, tồn tại đơn ánh g: X’  Y’ sao cho g(x) kề với x. Như vậy, ta có thể xây
dựng được đơn ánh h: X  Y sao cho h(x) kề với x: cụ thể h(x) = f(x) nếu x thuộc A và
h(x) = g(x) nếu x thuộc X \ A.
Quan hệ ≤ trên tập hợp X được gọi là một quan hệ thứ tự nếu thỏa mãn đồng thời các
điều kiện sau:
i) x ≤ x với mọi x thuộc X (tính phản xạ)
ii) Nếu x ≤ y, y ≤ x thì x = y (tính phản xứng)
iii) Nếu x ≤ y, y ≤ z thì x ≤ z (tính bắc cầu)
Một tập hợp mà trên đó xác định một quan hệ thứ tự được gọi là một tập sắp thứ tự.

i
thuộc vào
một M-đối xích nào đó trong X’. Dễ dàng thấy rằng A = {a
1
, a
2
, …, a
M
} là một đối xích
(nếu chẳng hạn a
i
< a
j
thì vì a
j
thuộc vào một M-đối xích nào đó và đối xích này lại chứa
một phần tử b
i
của C
i
nên theo tính lớn nhất của a
i
, ta có b
i
≤ a
i
< a
j
điều này mâu thuẫn vì
b

]}, S
+
{x ∈ X: ∃i [ a
i
≤ x]}
 Vì C là cực đại, phần tử lớn nhất của C không nằm trong S
-
.
 Theo giả thiết quy nạp, định lý đúng với S
-
.
 Vì thế, S
-
là hợp của M xích rời nhau S
-
1
, …, S
-
M
, trong đó a
i
∈ S
-
i
.
 Giả sử rằng x ∈ S
-
i
và x > a
i

kn đối tượng được chia ra.
Đây là một trong những nguyên lý không xây dựng (non-constructive) lâu đời nhất: nó chỉ nói đến sự tồn
tại của một chuồng trong đó có nhiều hơn k vật mà không nói gì đến cách tìm ra chuồng này. Ngày nay
chúng ta đã có những tổng quát hóa rất mạnh của nguyên lý này (các định lý kiểu Ramsey, phương pháp
xác suất…).
Mặc dù nguyên lý chuồng và thỏ được phát biểu rất đơn giản, nó có hàng loạt các ứng dụng không tầm
thường. Cái khó của việc ứng dụng nguyên lý này là xác định được xem thỏ là gì và chuồng là gì. Chúng
ta sẽ minh họa điều này bằng một số ví dụ.
1. Một số ví dụ mở đầu
Để khởi động, chúng ta sẽ bắt đầu bằng những ứng dụng đơn giản nhất. Bậc của một đỉnh trong đồ thị G
là số d(x) các cạnh của G kề với x.
Mệnh đề 1. Trong mọi đồ thị tồn tại hai đỉnh có cùng bậc.
Chứng minh. Giả sử ta có đồ thị G có n đỉnh. Ta tạo ra n cái chuồng được đánh số từ 0 đến n-1 và xếp
đỉnh x vào chuồng thứ k khi và chỉ khi d(x) = k. Nếu như trong một chuồng nào đó có nhiều hơn 1 đỉnh
thì ta có đpcm. Vì thế ta có thể giả sử rằng không có chuồng nào chứa hơn 1 đỉnh. Có tất cả n đỉnh được
chia vào n cái chuồng, nhưng vậy mỗi một chuồng có đúng 1 đỉnh. Gọi x và y là các đỉnh nằm trong các
chuồng đánh số 0 và n-1 tương ứng. Đỉnh x có bậc 0 vì vậy nó không được nối với các đỉnh khác, trong
đó có y. Nhưng y có bậc n-1 nên nó lại được nối với tất cả các đỉnh, trong đó có x, mâu thuẫn.
Nếu G là một đồ thị hữu hạn, chỉ số độc lập (independent number) α(G) là số lớn nhất các đỉnh đôi một
không kề nhau của G. Sắc số (chromatic number) χ(G) của G là số nhỏ nhất các màu cần dùng để tô các
màu của G sao cho không có hai đỉnh kề nhau được tô cùng màu.
Mệnh đề 2. Trong mọi đồ thị G với n đỉnh ta có n
≤

α
(G).
χ
(G).
Chứng minh. Ta chia các đỉnh của G thành χ(G) nhóm (các tập hợp các đỉnh có cùng màu). Theo nguyên
lý chuồng và thỏ, một trong các nhóm đó có chứa ít nhất n/χ(G) đỉnh, và các đỉnh này đôi một không kề

phần tử của A xuất hiện theo đúng thứ tự mà chúng xuất hiện trong A. Có nghĩa là B = (a
i1
, a
i2
,…, a
ik
) với
i
1
< i
2
< …< i
k
. Dãy con B được gọi là tăng nếu a
i1
< a
i2
<…< a
ik
, và giảm nếu a
i1
> a
i2
>…> a
ik
.
Ta quan tâm đến độ dài lớn nhất của dãy con tăng và giảm của A. Suy luận trực quan cho thấy phải có
một sự cân đối nhất định giữa hai độ dài này. Nếu như dãy con tăng dài nhất là ngắn, chẳng hạn có chiều
dài là s, thì mọi dãy con của A có độ dài s+1 phải chứa cặp phần tử giảm, như vậy có rất nhiều cặp phần
tử giảm. Vì thế ta trông đợi rằng dãy con giảm dài nhất sẽ lớn. Một trường hợp cực biên xảy ra khi s = 1.

. Chú ý rằng không có hai phần tử nào có cùng điểm số, tức là (x
i
, y
i
) ≠ (x
j
, y
j
) với mọi i
≠ j. Thật vậy, nếu ta có a
i
a
j
, thì hoặc a
i
< a
j
và dãy con tăng dài nhất kết thúc tại a
i
có thể kéo dài
đến a
j
(và do đó x
i
< x
j
), hoặc a
i
> a
j

i
, y
i
) ≠ (x
j
, y
j
) với mọi i ≠ j. Vì |A| = n ≥ rs + 1, ta có nhiều vật hơn là số chuồng thỏ được tô
đậm trong hình vẽ trên. Như vậy phải có một phần tử a
i
nằm ngoài miền tô đậm. Nhưng điều này có nghĩa
là x
i
≥ s+1 hoặc y
i
≥ r + 1 (hoặc cả hai), đúng điều chúng ta cần.
Tập hợp các số thực được sắp toàn phần. Điều này có nghĩa là với hai số phân biệt x, y thì hoặc x < y
hoặc y < x. Bổ đề dưới đây, thuộc về Dilworth, sẽ tổng quát hóa định lý Erdos-Szekeres cho các tập hợp
mà trong đó hai phần tử có thể không so sánh được.
Một thứ tự bộ phận (yếu) trên tập hợp P là quan hệ hai ngôi < giữa các phần tử của P. Ta nói hai phần tử
x và y là so sánh được nếu x < y hoặc y < x (hoặc cả hai). Một xích là một tập hợp Y ⊆ P sao cho hai
phần tử bất kỳ của Y là so sánh được. Nếu không có hai phần tử khác nhau nào của Y là so sánh được, thì
Y được gọi là đối xích.
Bổ đề 5 (Dilworth 1950). Trong mọi thứ tự bộ phận trên tập hợp P gồm n ≥ sr + 1 phần tử, tồn tại xích có
kích thước s+1 hoặc đối xích có kích thước r+1.
Chứng minh. Giả sử rằng không có xíc độ dài s+1. Khi đó ta có thể định nghĩa hàm số f: P  {1, , s}
trong đó f(x) là số phần tử lớn nhất của một xích có phần tử lớn nhất x. Theo nguyên lý chuồng và thỏ, sẽ
có r+1 phần tử của P có cùng ảnh qua ánh xạ f. Theo định nghĩa của f, các phần tử này không so sánh
được; và như vậy chúng tạo thành một đối xích có kích thước r+1.
Bài tập 5. Từ bổ đề Dilworh hãy suy ra định lý Erdos-Szekeres.

2
≤ …≤
x
n+1
và y
1
≤ y
2
≤ … ≤ y
n+1
3. Định lý Mantel
Dưới đây chúng ta sẽ thảo luận về một tính chất tối ưu đặc trưng của đồ thị. Một đồ thị G gồm 2n đỉnh
không chứa tam giác có thể có bao nhiêu cạnh? Tam giác là tập hợp {x, y, z} gồm ba đỉnh mà hai đỉnh bất
kỳ đều được nối với nhau bởi một cạnh. Dĩ nhiên là G có thể chứa n
2
cạnh mà không chứa tam giác: chỉ
cần lấy đồ thị hai phe đầy đủ gồm hai tập hợp mỗi tập hợp có n đỉnh và tất cả các cạnh nối giữa hai tập
hợp. Thực tế là n
2
chính là số cạnh lớn nhất có thể: nếu ta thêm một cạnh và đồ thị thì sẽ xuất hiện tam
giác.
Ta sẽ đưa ra 4 chứng minh cho kết quả đẹp đẽ này: chứng minh thứ nhất dùng nguyên lý chuồng và thỏ,
chứng minh thứ hai dựa trên phương pháp đếm bằng hai cách, chứng minh thứ ba sử dụng bất đẳng thức
AM-GM và chứng minh thứ tư sử dụng “lý luận dịch chuyển“ (ta sẽ đề cập tới chứng minh này trong
phần sau).
Định lý 6 (Mantel 1907). Nếu đồ thị G với 2n đỉnh có n
2
+1 cạnh thì G chứa tam giác.
Chứng minh thứ nhất. Ta chứng minh bằng quy nạp theo n. Với n = 1, thì G không thể có n
2

2)( =
∑
∈
, ta được
∑
∑
∈
∈
=






≥=
Vx
Vx
n
m
V
xd
xd .
2
||
)(
)(
2
2
2



+
≤≤≤
∑
∈
4. Định lý Turan
Một k-clique là một đồ thị với k đỉnh mà hai đỉnh bất kỳ đều được nối với nhau bởi một cạnh. Ví dụ tam
giác là 3-clique. Định lý Mantel khẳng định rằng nếu đồ thị với n đỉnh không chứa 3-clique thì nó có
nhiều nhất n
2
/4 cạnh. Còn nếu k > 3 thì sao?
Câu trả lời được cho bởi kết quả cơ bản của Paul Turan, kết quả đã mở đầu cho lý thuyết đồ thị tối ưu.
Định lý 7 (Turan 1941). Nếu đồ thị G = (V, E) trên n đỉnh không chứa (k+1)-clique, k
≥
2, thì
.
2
1
1||
2
n
k
E







.
2
)(1
1
2
kn
k
e
B
−






−≤
Vì G không có k+1 clique nên mỗi x ∈ B kề với nhiều nhất k-1 đỉnh thuộc A, và ta thu được
e
A,B
≤ (k-1)(n-k).
Cộng các bất đẳng thức này lại và sử dụng đẳng thức
2
2
2
2
2
1
1


11
2
))(1(
2
22
||
2
2
2
,
n
kk
kn
k
knk
kn
kk
eeeE
BABA






−=













≤++≤
Bài tập 7. Giả sử rằng n là bội số của k. Hãy xây dựng một đồ thị không chứa (k+1)-clique, trong đó số
các cạnh đạt được cận trên (1) trong định lý 7.
Bài tập 8. Nhắc lại chỉ số độc lập α(G) của đồ thị G là số lớn nhất các đỉnh đôi một không kề nhau của G.
Hãy chứng minh đối ngẫu của định lý Turan: Nếu G là đồ thị với n đỉnh và nk/2 cạnh, k ≥ 1, thì α(G) ≥
n/(k+1).
5. Định lý Dirichlet
Ở đây ta trình bày một ứng dụng của nguyên lý chuồng và thỏ mà Dirichlet đã sử dụng, và chính vì ứng
dụng này mà nguyên lý này được gắn với tên ông. Nó liên quan đến vấn đề tồn tại xấp xỉ hữu tỷ tốt cho
các số vô tỷ. Kết quả này thuộc về lý thuyết số nhưng lý luận là tổ hợp.
Định lý 8 (Dirichlet 1879). Nếu x là một số thực. Với mỗi số nguyên dương n,tồn tại số hữu tỷ p/q sao
cho 1
≤
q
≤
n và
.
11
2
q
nqq
p




n
n
nnn

(Không có số nào trong các số nói trên trùng với đầu mút các đoạn, vì x là vô tỷ). Theo nguyên lý chuồng
và thỏ, có một đoạn nào đó chứa nhiều hơn một số, vì dụ là {ax} và {bx}với a > b, và do đó cách nhau
không quá 1/n. Đặt q = a – b, ta thấy rằng tồn tại số nguyên p sao cho |qx – p| < 1/n, từ đó suy ra kết quả
cần chứng minh bằng cách chia cho q. Hơn nữa, q là hiệu của hai số nguyên thuộc 1, 2, …, n+1, do đó q ≤
n.

6. Đồ thị được tô đặc sắc
Ta tô màu các cạnh của đồ thị đầy đủ K
n
trên n đỉnh. Ta nói rằng đồ thị được tô đặc sắc (swell-colored)
nếu mọi tam giác chứa 1 hoặc 3 màu, nhưng không chứa 2 màu và đồ thị có nhiều hơn một màu. Có nghĩa
là, ta cần sử dụng ít nhất 2 màu và với mọi tam giác, hoặc là tất cả các cạnh của nó có cùng màu hoặc có
màu khác nhau.
Ta có thể chứng minh được rằng (hãy chứng minh!) K
n
không thể được tô đặc sắc với đúng hai màu.
Cũng có thể thấy rằng K
3
và K
4
là những đồ thị K
n
duy nhất có thể tô đặc sắc với 3 màu; các đồ thị K

là các đỉnh kề với x
0
bởi N cạnh có màu c
0
. Gọi G là đồ thị con (đầy đủ) của K
n
cảm sinh
từ tập hợp các đỉnh {x
0
, x
1
, , x
N
}. Tính đặc sắc của K
n
được cảm sinh cho G và như vậy mọi cạnh của G
có cùng màu c
0
. Vì K
n
có ít nhất hai màu nên tồn tại đỉnh y thuộc K
n
không nằm trong G và sao cho ít
nhất một cạnh nối y với G có màu khác c
0
.
Khẳng định 10. N+1 cạnh nối y tới G được tô màu khác nhau và khác với c
0
.
Từ khẳng định này ta suy ra r ≥ N + 2, từ đó, cùng với bất đẳng thức N.r ≥ n – 1 suy ra r(r-2) ≥ n – 1, và

ta có cạnh {x
1
, x
2
} cũng được tô bằng màu đó. Nhưng {x
1
, x
2
} thuộc G và có màu c
0
và như
vậy {y, x
1
} phải có màu c
0
là điều mà ta đã chứng minh ở trên là không thể. Điều này kết thúc phép chứng
minh khẳng định và cũng là kết thúc chứng minh định lý.
Tính tối ưu của cận dưới cho bởi định lý 9 có thể được chứng tỏ sử dụng một cấu hình gọi là “mặt phẳng
afine”. Ta hiểu rằng mặt phẳng afine AG(2,q) bậc q chứa đúng q
2
điểm và đúng q+1 lớp (được gọi là “bút
chì”) các đường thẳng song song, mỗi lớp chứa q đường thẳng (hai đường thẳng là song song nếu chúng
không có điểm chung). Hơn nữa, hai điểm bất kỳ nằm trên đúng một đường thẳng.
Khi có 1 mặt phẳng như vậy, ta có thể xây dựng một phép tô đặc sắc cho
2
q
K
với q+1 màu như sau. Ta
đồng nhất các đỉnh của
2