ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
HỒ HUYỀN TRANG
LÍ THUYẾT ĐỒ THỊ VÀ GIẢ
THUYẾT ERD
¨
OS - SZEKERES
LUẬN VĂN THẠC SỸ TOÁN HỌC
Chuyên ngành : TOÁN ỨNG DỤNG
Mã số : 60 46 36
Giáo viên hướng dẫn:
PGS. TS. TẠ DUY PHƯỢNG
THÁI NGUYÊN, 2011
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn
Mục lục
1 Khái niệm đồ thị 5
1.1 Định nghĩa đồ thị . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Đường đi và chu trình . . . . . . . . . . . . . . . . . . . . . 6
1.3 Chu số và sắc số của đồ thị . . . . . . . . . . . . . . . . . . 9
1.3.1 Chu số của đồ thị . . . . . . . . . . . . . . . . . . . 9
1.3.2 Sắc số của đồ thị . . . . . . . . . . . . . . . . . . . 10
1.4 Chu trình Euler và chu trình Hamilton . . . . . . . . . . . . 17
1.4.1 Chu trình Euler . . . . . . . . . . . . . . . . . . . . 17
1.4.2 Chu trình Hamilton . . . . . . . . . . . . . . . . . . 20
2 Lý thuyết đồ thị, Định lý Ramsey và Giả thuyết Erd¨os -
Szekeres 25
2.1 Định lý Ramsey dưới ngôn ngữ đồ thị . . . . . . . . . . . . 25
2.2 Chứng minh định lí Ramsey nhờ ngôn ngữ đồ thị . . . . . . 28
2.3 Định lí Ramsey và chứng minh Giả thuyết Erd¨os - Szekeres 34
2.3.1 Lịch sử bài toán Erd¨os-Szekeres . . . . . . . . . . . 34
2.3.2 Định lí Ramsey dưới ngôn ngữ tập hợp . . . . . . . 37

đỉnh và các cạnh được tô bởi hai màu đỏ và xanh. Chứng minh rằng có
ít nhất ba cạnh đồng màu (hoặc đỏ hoặc xanh). Bài toán này cũng có thể
phát biểu dưới ngôn ngữ trò chơi như sau: Có sáu người ngồi quanh bàn
tiệc, hãy chứng tỏ rằng có ít nhất hoặc ba người đôi một quen nhau hoặc
đôi một không quen nhau.
Do bản chất triết học sâu sắc, Định lí Ramsey đã trở thành hòn đá tảng
của Lí thuyết Ramsey và có rất nhiều ứng dụng trong toán học và thực tế
(lí thuyết số, hình học tổ hợp, lí thuyết đồ thị, lí thuyết mạng, toán trò
chơi, trong công nghệ thông tin, ).
Một điều thú vị là, gần đây (2011), các tác giả của [10] đã sử dụng Định
lí Erd¨os -Szekeres suy rộng để trả lời một câu hỏi mở của giả thuyết "big
3
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn
line and big clique" trong lí thuyết đồ thị (xem [10]).
Như vậy, lí thuyết đồ thị, Định lí Ramsey và giả thuyết Erd¨os -Szekeres có
mối quan hệ khá chặt chẽ và thú vị.
Cơ bản dựa trên bài báo [10], luận văn Lí thuyết Đồ thị và Giả thuyết
Erd¨os -Szekeres cố gắng phác thảo mối quan hệ thú vị giữa ba đối tượng
toán học trên.
Luận văn gồm 3 chương:
Chương 1 : Trình bày các khái niệm cơ bản lí thuyết đồ thị. Các định
nghĩa và định lí của Chương này sẽ được sử dụng trong hai chương sau.
Chương 2 : Trình bày giả thuyết Erd¨os -Szekeres các chứng minh Định lí
Ramsey.
Chương 3 :Dựa trên tài liệu [10], trình bày chứng minh Định lí Erd¨os -
Szekeres suy rộng và áp dụng để trả lời một câu hỏi mở của giả thuyết
"big line or big clique" trong lí thuyết đồ thị.
Luận văn được hoàn thành dưới sự hướng dẫn của PGS TS Tạ Duy Phượng.
Tác giả xin bày tỏ lòng kính trọng và biết ơn thầy hướng dẫn đã tận tình
giúp đỡ, giảng giải trong suốt quá trình tác giả học tập và nghiên cứu đề

các cạnh E = {(a, b), (a, c), (b, c), (d, b), (d, c), (e, a), (e, b), (e, d)}.
Nếu (a, b) là một cạnh của đồ thị thì ta nói rằng đỉnh b kề với đỉnh a và
cả hai đỉnh a và b kề với cạnh (a, b).
5
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn
Cặp đỉnh (x, y) ∈ E không sắp thứ tự được gọi là cạnh vô hướng, còn
nếu có sắp thứ tự được gọi là cạnh có hướng. Vì thế, ta thường phân các
đồ thị thành hai lớp: Đồ thị vô hướng và đồ thị có hướng.
Định nghĩa 1.1.2. Đồ thị chỉ chứa các cạnh vô hướng được gọi là đồ thị
vô hướng, còn nếu đồ thị chỉ chứa các cạnh có hướng được gọi là đồ thị có
hướng.
Định nghĩa 1.1.3. Đồ thị G = (V, E) được gọi là đối xứng nếu:
∀x, y ∈ V : (x, y) ∈ E ⇔ (y, x) ∈ E
.
Nhận xét:Các đồ thị vô hướng là đối xứng.
Định nghĩa 1.1.4. Đồ thị G = (V, E) mà mỗi cặp đỉnh được nối với nhau
bởi không quá một cạnh được gọi là đơn đồ thị (thường gọi tắt là đồ thị).
Còn nếu những cặp đỉnh được nối với nhau nhiều hơn một cạnh thì được
gọi là đa đồ thị.
1.2 Đường đi và chu trình
Giả sử G = (V, E) là một đồ thị.
Định nghĩa 1.2.1. Đường đi trong đồ thị là một dãy các đỉnh: x
1
, x
2
, , x
i
, x
i+1
, , x

, x
k
]
6
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn
trong đó x
1
= x
k
.
Để cho gọn, ta kí hiệu chu trình là
[x
1
, x
2
, , x
i
, x
i+1
, , x
k−1
] .
Khi nói đến một chu trình, nhiều khi ta cũng không cần xác định điểm
đầu và điểm cuối của nó.
Chu trình được gọi là chu trình đơn nếu các đỉnh trên nó khác nhau
từng đôi.
Trong một đồ thị, đỉnh nút là đỉnh kề với chính nó. Đỉnh cô lập là đỉnh
mà không có các đỉnh khác kề với nó. Tập m - độc lập là một đồ thị của
m - đỉnh cô lập.
Định nghĩa 1.2.3. i) Đồ thị G

Một đồ thị G được gọi là p− liên thông nếu như G liên thông và vẫn còn
là đồ thị liên thông nếu như ta bỏ đi ít hơn p đỉnh tùy ý cùng với các cạnh
kề với các đỉnh này.
Định nghĩa 1.2.5. Bậc của một đỉnh là số cạnh kề với đỉnh đó và thường
kí hiệu d(a) là bậc của đỉnh a trong đồ thị G. Bậc của đồ thị là số các
đỉnh, thường được kí hiệu là n.
Định lý 1.2.1. Tổng tất cả các bậc của đỉnh trong một đồ thị bằng hai
lần số cạnh của đồ thị đó.
Chứng minh. Ta tính bậc của đỉnh. Mỗi đỉnh thuộc một cạnh nào đó
thì bậc của nó tăng thêm 1. Mà mỗi cạnh thì có hai đỉnh. Do đó tổng tất
cả các bậc của đỉnh là gấp đôi số cạnh của đồ thị.
Hệ quả 1.2.1. Số đỉnh có bậc lẻ trong một đồ thị phải là một số chẵn.
Định lý 1.2.2. Đồ thị G có n đỉnh. Nếu bậc của mỗi đỉnh trong G không
nhỏ hơn
n
2
thì đồ thị G liên thông.
Chứng minh Ta chứng minh bằng phản chứng.
Giả sử đồ thị G liên thông. Khi đó có ít nhất hai đỉnh a và b nằm trong
hai mảng liên thông khác nhau. Vậy thì, n ≤ d(a) + d(b) ≤ n −2. Suy ra
điều mâu thuẫn.
Một số tính chất của bậc của một đỉnh
Đỉnh có bậc 0 được gọi là đỉnh cô lập (isolated vertex).
Đỉnh có bậc 1 được gọi là đỉnh treo, cạnh tới đỉnh treo gọi là cạnh treo.
Đồ thị mà mọi đỉnh đều là đỉnh cô lập gọi là đồ thị rỗng.
Đồ thị được gọi là đồ thị phẳng nếu nó có thể biểu diễn được trên mặt
phẳng sao cho không có hai đường biểu diễn nào cắt nhau.
Đồ thị được gọi là đồ thị đầy đủ nếu hai đỉnh bất kì đều có cạnh nối, tức
là mỗi đỉnh của đồ thị đều kề với mọi đỉnh khác. Ta kí hiệu K
n

Chứng minh Thật vậy, đồ thị G được xây dựng từ đồ thị G
0
gồm n
đỉnh và không có cạnh nào cả. Sau đó lần lượt thêm các cạnh vào đồ thị
G
0
để được đồ thị G.
Chu số của G
0
là c = 0 −n +n = 0. Quá trình thêm cạnh không làm giảm
chu số. Vậy chu số của G lớn hơn hoặc bằng chu số của G
0
= 0.
1.3.2 Sắc số của đồ thị
Khái niệm sắc số liên quan đến bài toán tô màu đồ thị như sau:
Hãy tô màu các đỉnh của đồ thị đã cho, sao cho hai đỉnh kề nhau phải
được tô bằng hai màu khác nhau.
Ta nói rằng, đồ thị G tô được bằng k màu nếu tồn tại hàm
m : V → {0, 1, 2, , k − 1}
sao cho, nếu hai đỉnh x và y kề nhau thì m(x) = m(y).
Dễ thấy rằng, đồ thị G tô màu được khi và chỉ khi nó không có đỉnh nút.
Định nghĩa 1.3.2. Sắc số của một đồ thị chính là số màu ít nhất dùng
để tô màu các đỉnh của đồ thị đó.
Ta kí hiệu χ (G) là sắc số của đồ thị G. Hiển nhiên χ (G) ≤ n. Nghĩa là
sắc số (số màu) không vượt quá số đỉnh của đồ thị.
Tập B ⊆ V được gọi là tập ổn định trong của đồ thị G nếu: ∀x ∈ B :
B ∩F (x) = ∅
Nhận xét Mỗi cách tô màu m cho đồ thị G ứng với một cách phân
hoạch tập đỉnh V thành các tập ổn định trong không giao nhau, mỗi tập
ứng với một màu. Ngươc lại, mỗi cách phân hoạch tập đỉnh V thành các

toàn các cạnh sao cho:
∀x, y ∈ V
1
, (x, y) ∈ E
1
⇔ (S(x), S(y)) ∈ E
2
.
Ví dụ: Hai đồ thị dưới đây là đẳng hình với song ánh:
S(a
i
) = x
i
, i = 1, 2, 3, 4.
11
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn
Hình 1.6 Hai đồ thị đẳng hình.
Định lý 1.3.2. Nếu G chứa một đồ thị con đẳng hình với K
m
thì χ (G) ≥
m.
Ví dụ 1.7 Hãy tô màu đồ thị sau:
Hình 1.7 Tô màu các đỉnh của đồ thị.
Đồ thị trên có sắc số bằng 3.
Nhận xét Có hai điều kiện lưu ý khi tìm sắc số của đồ thị G.
Nếu G

⊆ G thì χ (G

) ≤ χ (G) .

với x
2n+1
ta được một chu trình có độ dài 2n + 1. Theo giả thiết
quy nạp, chu trình α

có sắc số bằng 3. Lấy màu của x
1
tô cho x
2n+2
, còn
màu của x
2n+1
tô cho x
2n+3
. Chu trình α đã được tô màu mà không phải
thêm màu mới. Vậy, chu trình α có sắc số bằng 3.
Định lý 1.3.5. (K¨onig) Giả sử đồ thị G có ít nhất một cạnh. Đồ thị G là
hai sắc (có sắc số là 2) khi và chỉ khi G không có chu trình đơn vô hướng
độ dài lẻ.
Chứng minh:
(⇒) Hiển nhiên. Giả sử G là đồ thị hai sắc. Theo định lý 1.3.4 thì G không
thể có chu trình đơn vô hướng độ dài lẻ.
(⇐) Giả sử G không có chu trình đơn vô hướng độ dài lẻ. Ta sẽ chứng
minh rằng ta có thể tô màu các đỉnh của đồ thị G bằng hai màu.
Không mất tính tổng quát, ta có thể giả sử G liên thông. Chọn một đỉnh
v
0
∈ G. Ta tô màu các đỉnh của G bằng hai màu đánh số 0 và 1 theo cách
sau:
Với mỗi đỉnh x có một đường trong G nối v

) ≤ χ (G) + 1. Giả sử
bâc cao nhất của các đỉnh trong G

là d

. Hiển nhiên d ≤ d

.
Nếu χ (G) ≤ d thì χ (G) ≤ d + 1 ≤ d

+ 1.
Nếu χ (G) = d+1 thì: Trường hợp: d ≤ d

ta có : χ (G) ≤ d+1+1 ≤ d

+1.
Hình 1.7 Cách chọn màu cho đỉnh mới.
Trường hợp d = d

thì đỉnh mới a được nối với không quá r đỉnh. Do
vậy, chỉ cần giữ nguyên cách tô màu của G thì các đỉnh kề với a được
tô không quá r màu và vẫn còn thừa một màu dành cho đỉnh a. Suy ra:
χ (G

) ≤ χ (G) ≤ d + 1 = d

+ 1.
Hệ quả 1.3.3. (Định lí Brook) Nếu G là một đồ thị liên thông với bậc lớn
nhất d, thì ta có χ (G) ≤ d(G) nếu như G không phải là đồ thị đầy đủ và
không phải là chu trình lẻ cạnh.

Tô màu cho đồ thị mới bằng 5 màu, do giả thiết quy nạp nên điều này
thực hiện được. Bây giờ ta đưa đỉnh x vào lại đồ thị.
Nếu các đỉnh kề với x được tô bằng ít hơn 5 màu thì tô màu x bằng một
trong 5 màu khác màu các đỉnh kề với x là xong. Đồ thị G đã được tô
bằng 5 màu.
Ta chỉ xét trường hợp d(x) = 5 và 5 đỉnh kề với x được tô bằng 5 màu
15
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn
như Hình 1.9
Hình 1.9 Năm đỉnh kề với năm màu
Xét tất cả các đường trong G bắt đầu từ a và gồm các đỉnh chỉ tô bằng
màu 1 và màu 3. Trong các đường này, nếu không có đường nào đi qua
đỉnh c thì ta có thể thay đổi màu các đỉnh trên tất cả các đường nói trên
theo cách đổi màu 1 cho 3 và ta có thể tô đỉnh x màu 1.
Nếu có một đường từ a đến c gồm toàn các đỉnh chỉ tô màu 1 và màu
3 thì đường này cộng thêm hai cạnh ¯a¯x và ¯c¯x sẽ tạo thành một chu trình,
hai đỉnh b, d không thể nằm cùng bên trong hoặc cùng bên ngoài chu trình
này được. Suy ra, không có đường nào từ b đến d gồm các đỉnh chỉ tô màu
bằng màu 2 và màu 4. Vậy lại có thể thay đổi màu các đỉnh trên tất cả
các đường bắt đầu từ b gồm các đỉnh chỉ tô màu 2 và màu 4 theo cách đổi
màu 2 thành màu 4 và ngược lại. Lúc này, b và d có cùng màu 4 và ta có
thể tô đỉnh x bằng màu 2.
Bài toán bốn màu Trên một bản đồ bất kì, ta nối nó được tô màu
nếu mỗi miền của nó được tô miền xác định sao cho hai miền kề nhau
(chung một phần biên) phải được tô bằng hai màu khác nhau. Vấn đề đặt
ra là cần dùng tối thiểu bao nhiêu màu để tô một bản đồ bất kì đã được
đặt ra từ khoảng giữa thế kỉ 19. Mô hình toán học của bài toán như sau.
Với mỗi bản đồ M cho trước, ta xây dựng một đồ thị G tương ứng: Mỗi
miền của M ứng với một đỉnh của G, hai miền của M có chung một phần
biên nếu và chỉ nếu hai đỉnh tương ứng trong G có cạnh nối. Dễ thấy rằng

17
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn
Vào năm 1736, Euler (1707 - 1783) nhà toán học người Thụy Sĩ đã
chứng minh không thể có cách đi qua cả bảy cây cầu, mỗi cái đúng một
lần rồi quay về điểm xuất phát bằng lập luận sau.
Biểu diễn bốn miền đất A, B, C, D bằng điểm trong mặt phẳng, mỗi cầu
nối hai miền được biểu diễn bằng một đoạn nối hai điểm tương ứng, ta sẽ
có đồ thị.
Bây giờ một đường đi qua 7 cây cầu, mỗi cái đúng một lần rồi quay về
điểm xuất phát sẽ có số lần đi đến A bằng số lần rời khỏi A, nghĩa là phải
sử dụng đến một số chẵn cây cầu nối với A. Mà do số cầu nối đến A là 5
(lẻ) nên không có đường đi nào thỏa mãn điều kiện của bài toán.
Định lý 1.4.1. (Định lí Euler 1)
Cho một đồ thị vô hướng G liên thông và có hơn một đỉnh thì G có chu
trình Euler nếu và chỉ nếu mọi đỉnh của G đều có bậc chẵn.
Chứng minh (⇒) Mỗi lần chu trình đi qua một đỉnh thì đỉnh đó bớt
đi hai cạnh kề. Cuối cùng số cạnh kề của mỗi đỉnh bằng 0. Do đó, số cạnh
kề với mỗi đỉnh phải là số chẵn.
(⇐) Xuất phát từ một đỉnh a nào đó, ta lập dãy cạnh kề liên tiếp cho đến
khi hết khả năng đi tiếp. Khi dừng phải ở đỉnh a vì bậc các đỉnh đều chẵn,
ta thu được chu trình C
1
. Nếu đã vét hết các cạnh thì đó là chu trình cần
tìm. Nếu vẫn còn cạnh thì theo tính liên thông của đồ thị phải có một
cạnh nào đó chưa được chọn và kề với đỉnh a
1
nào đó của chu trình đã có.
Lại xuất phát từ a
1
và tiếp tục quá trình như trên cho đến khi hết khả


sẽ không có đỉnh bậc lẻ nên theo định lí
1.18 G

sẽ có chu trình Euler vô hướng. Bỏ cạnh (a, b) đi ta có đường đi
Euler vô hướng trong đồ thị G.
Định lý 1.4.3. (Định lí Euler 3)
Cho một đồ thị có hướng G liên thông và có hơn một đỉnh thì G có chu
trình Euler nếu và chỉ nếu G cân bằng (số cạnh đi vào bằng số cạnh đi
ra), nghĩa là: ∀x ∈ X : d
−
(x) = d
+
(x) trong đó d
−
(x) là số cạnh đi vào
đỉnh x và d
+
(x) là số cạnh đi ra khỏi x.
Định lý 1.4.4. (Định lí Euler 4)
Cho một đồ thị có hướng G liên thông và có hơn một đỉnh thì G có chu
trình Euler nếu và chỉ nếu G có hai đỉnh a, b thỏa mãn:
d
−
(a) = d
+
(a) −1
và
d
+

(a) −1
và
d
+
(b) = d
−
(b) + 1,
còn mọi đỉnh còn lại đều cân bằng. Ta thêm vào một cạnh mới (b, a). Khi
đó, mọi đỉnh là cân bằng nên theo Định lí Euler 3 thì đồ thị có chu trình
Euler có hướng. Bây giờ bỏ cạnh (b, a) khỏi chu trình thì ta được một
đường đi Euler có hướng.
1.4.2 Chu trình Hamilton
Năm 1857, W. R. Hamilton(1805 - 1865), nhà toán học người Ailen đã
đưa ra trò chơi sau đây: Trên mỗi đỉnh trong số hai mươi đỉnh của một
khối đa diện 12 mặt ngũ giác đều có ghi tên một thành phố lớn của thế
giới. Hãy tìm cách đi bằng các cạnh của khối này để đi qua tất cả các
thành phố, mỗi thành phố đúng một lần.
Bài toán này dẫn đến những khái niệm sau đây.
Định nghĩa 1.4.2. Xét một đồ thị có hướng G liên thông và có hơn một
đỉnh.
Một đường Hamilton là đường đi qua mỗi đỉnh của đồ thị đúng một lần.
Chu trình Hamilton là chu trình đi qua mỗi đỉnh của đồ thị đúng một lần.
Đồ thị G được gọi là Đồ thị Hamilton nếu nó chứa chu trình Hamilton và
gọi là đồ thị nửa Hamilton nếu nó có đường đi Hamilton.
Rõ ràng, một đồ thị Hamilton là nửa Hamilton, nhưng điều ngược lại
không còn đúng.
20
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn
Ví dụ 1.9 Tổ chức tour du lịch sao cho người du lịch thăm quan mỗi
thắng cảnh trong thành phố đúng một lần.

(H) = (x
1
, x
2
, , x
n
).
Nếu trong G có cạnh (x
n
, a) thì đường ((H), a) sẽ là đường Hamilton.
Nếu trong G có cạnh (a, x
1
) thì đường (a, (H)) sẽ là đường Hamilton.
Trong trường hợp ngược lại, đồ thị G phải có các cạnh (x
1
, a) và (a, x
n
)
nghĩa là có các cạnh ngược hướng nhau. Khi đó sẽ phải có ít nhất một cặp
cạnh sát nhau nhưng ngược hướng nhau là (x
i
, a) và (a, x
i+1
).
21
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn
Hình 1.12 Cách tìm đường đi Hamilton.
Ta có đường đi (x
1
, x

q
) ≥ q + 1 thì đồ thị con G

tạo bởi tập đỉnh {a
0
, a
1
, , a
q
}
có chu trình vô hướng Hamilton.
Chứng minh Kí hiệu d

(a) là bậc của đỉnh a trong G

. Vì đường đi
đơn là cực đại nên d

(a
0
) = d(a + 0); d

(a
q
) = d(a
q
).
22
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn
Hình 1.13 Cách tìm chu trình Hamilton.

) ≤ q − k. Do đó,
d(a
0
) + d(a
q
) ≤ q (trái với giả thiết).
Vậy, phải có ít nhất một đỉnh a
i−1
sao cho a
0
kề với a
i
và a
q
kề với a
i−1
.
Khi đó, dãy các đỉnh [a
0
, a
i
, , a
q
, a
i−1
, , a
0
] là một chu trình vô hướng
của G.
Định lý 1.4.7. Giả sử đồ thị G có n đỉnh.

Lý thuyết đồ thị, Định lý Ramsey
và Giả thuyết Erd
¨
os - Szekeres
2.1 Định lý Ramsey dưới ngôn ngữ đồ thị
Trước tiên ta nhắc lại nguyên lí Dirichlet (Nguyên lý chuồng chim bồ
câu)
Nguyên lý chuồng chim bồ câu
Định lý 2.1.1. Nếu một tập s phần tử được phân hoạch thành n tập con
rời nhau, với s > n, thì ít nhất một trong các tập con có nhiều hơn một
phần tử.
Nguyên lí chuồng chim bồ câu có liên quan mật thiết với bài toán sau
đây.
Bài toán 1 Trong một bữa tiệc có một số người đôi một quen nhau
hoặc đôi một không quen nhau. Hỏi số người ít nhất trong bữa tiệc là bao
nhiêu để tồn tại ít nhất ba người đôi một quen nhau hoặc đôi một không
quen nhau?
Ta định nghĩa khái niệm "đôi một quen nhau” như sau: A quen B ⇔ B
quen A.
Giải Xét 6 điểm trên mặt phẳng.Ta dùng đoạn nối liền giữa hai điểm
thể hiện sự quen nhau và hai điểm nối nét đứt với nhau chỉ sự không quen
nhau (Hình vẽ).
Bây giờ ta xét sáu điểm O, A, B, C, D, E. Xét điểm O.
25
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn