SỞ GIÁO DỤC VÀ ĐÀO TẠO LÀO CAI
TRƯỜNG TRUNG HỌC PHỔ THÔNG CHUYÊN LÀO CAI

ĐỊNH LÝ MANTEL
VÀ BÀI TOÁN VMO 2017
Giáo viên: Nguyễn Quang Tân
Tổ: Toán – Tin

Lào Cai, năm học 2017 - 2017
1


Mục lục
A. LÝ DO CHỌN VIẾT CHUYÊN ĐỀ .............................................................................................................. 2
B. NỘI DUNG ................................................................................................................................................ 3
1. Khái niệm đồ thị ................................................................................................................................... 3
2. Đồ thị đầy đủ, đồ thị hai phần .............................................................................................................. 5
3. Định lý Mantel – Turan ........................................................................................................................ 6
TÀI LIỆU THAM KHẢO .............................................................................................................................. 14

A. LÝ DO CHỌN VIẾT CHUYÊN ĐỀ
Trước đây phần lý thuyết đồ thị thường không được dạy cho học sinh trong việc bồi
dưỡng học sinh giỏi nhưng trong kì thi VMO 2017 có bài toán số 4 như sau:

Cho số nguyên n  1 . Bảng vuông ABCD  kích thước n  n gồm n 2 ô vuông đơn vị , mỗi ô
vuông đơn vị được tô bởi ba màu : đen, trắng, xám . Một cách tô màu được gọi là đối xứng
nếu mỗi ô có tâm trên đường chéo AC được tô màu xám và mỗi cặp ô đối xứng qua AC
được tô màu đen hoặc cùng màu trắng. Người ta điền vào mỗi ô xám số 0 , mỗi ô trắng một
số nguyên dương và mỗi ô đen một số nguyên âm . Một cách điền số như vậy được gọi là
k  cân đối (với k là số nguyên dương) nếu thỏa mãn các điều kiện sau:
(i) Mỗi cặp ô đối xứng qua AC được điền cùng một số nguyên thuộc đoạn  k ; k .

(ii) Nếu một hàng và một cột giao nhau tại ô đen thì tập các số nguyên dương được điền
trên hàng đó và tập số nguyên dương được điền trên cột đó không giao nhau;nếu một hàng
và một cột giao nhau tại ô trắng thì tập các số nguyên âm được điền trên hàng đó và tập các
số nguyên âm được điền trên cột đó không giao nhau.
a)Với n  5 , tìm giá trị nhỏ nhất của k để tồn tại cách điền hình số k  cân đối cho cách tô
màu như hình bên dưới.

2


b)Với n  2017 , tìm giá trị nhỏ nhất của k để với mọi cách tô màu đối xứng , luôn tồn tại
cách điền k cân đối.
Thật khó để giải bài toán này nếu không đưa về ngôn ngữ đồ thị và sử dụng định lý Mantel –
Turan, do vậy cần thiết phải giới thiệu cho học sinh một số kiến thức cơ bản về lý thuyết đồ
thị.
Trong chuyên đề này người viết chọn giới thiệu một phần kiến thức cơ bản về lý thuyết đồ
thị bao gồm:
1. Khái niệm đồ thị, đỉnh, bậc và một số kiến quả cơ bản;
2. Đồ thị đầy đủ, đồ thị hai phần;
3. Định lý Mantel – Turan.
Qua đó học sinh có thể giải được một số bài tập về đồ thị liên quan tới các vấn đề trên,
trong đó có đề thi VMO 2017 vừa rồi.
B. NỘI DUNG
1. Khái niệm đồ thị
Định nghĩa 1.
Một đồ thị là một bộ G  (V , E ) trong đó V là tập đỉnh và E là tập
hợp các cạnh nối các đỉnh trong V .

Định nghĩa 2.
Ta nói rằng hai đỉnh v, w là kề nhau nếu tồn tại một cạnh nối v và w .

Định nghĩa 3.
Cho một đỉnh v , bậc của v là số cạnh nhận v là đầu mút, kí hiệu là
d (v).
Định lý 1. (Handsack). Cho đồ thị G có n đỉnh, m cạnh và bậc của n đỉnh là d1 ,, dn thì
n

d

i

 2m

i 1

Chứng minh
Ta sử dụng kĩ thuật đếm bằng 2 cách.
Ta đếm số bộ ( v , e ) trong đó v là đỉnh và e là cạnh v làm đầu mút.
n

Nếu đếm theo v thì s   di .
i 1

Nếu đếm theo e trước thì s  2m .
3


Hệ quả 1.
i) Trong một đồ thị có chẵn đỉnh bậc lẻ.
ii) Trong một đồ thị có lẻ đỉnh thì sẽ có một đỉnh bậc chẵn.
Nhận xét. Bậc nhỏ nhất 


2| E |
 bậc lớn nhất.
|V |

Bài toán 1. (Vũ Đình Hòa). Trong một lớp có 20 học sinh. Chứng minh rằng tồn tại 2 em mà
số bạn chúng là một số chẵn.

Lời giải.
Xét đồ thị G gồm 20 đỉnh là các học sinh và các cạnh là quan hệ quen biết giữa các học sinh.
TH1: Tồn tại một em học sinh A0 có lẻ bạn là A1, A2 , A2t 1
Xét đồ thị tạo bởi các đỉnh A1, A2 , A2t 1 , đồ thị này có lẻ đỉnh lên phải có một đỉnh bậc chẵn
là Ai0 . Nên A0 và Ai0 có chẵn bạn chung.
TH2: Tồn tại một học sinh A0 có chẵn bạn là A1 ,, A2t .
Xét đồ thị tạo G1 bởi các đỉnh A1 ,, A2t nếu trong đồ thị này có một đỉnh bậc chẵn Ai0 thì
bài toán được giải quyết.
Nếu trong đồ thị G1 không có đỉnh nào bậc chẵn thì ta bổ sung thêm một đỉnh B khác A0
vào G1 được một đồ thị là G2 , đồ thị này có lẻ đỉnh nên phải có một đỉnh bậc chẵn. Đỉnh đó
chính là B . Vậy khi có A0 và B có chẵn bạn chung.
Bài toán 2. Có 30 cặp phụ huynh đi họp. Mỗi người bắt tay một số người khác (không bắt
tay vợ hoặc chồng mình). Ông A quan sát thấy số cái bắt tay của những người còn lại đều
khác nhau đôi một. Hỏi vợ chồng ông A bắt tay bao nhiêu người?
Giải
Xây dựng đồ thị tập đỉnh ứng 60  người, mỗi cạnh là một cái bắt tay. Vì mỗi người không
bắt tay với vợ hoặc chồng mình nên 0  bậc của các đỉnh  58 . Vì ngoài ông A, số bắt tay của
những người còn lại đôi một khác nhau nên số bắt tay của những người còn lại là 0,1,  , 58 .
Gọi Ai là đỉnh có bậc là i với 0  i  58 .


Ta thấy A0 không bắt tay với A58 . Còn A58 thì bắt tay với tất cả mọi người trừ vợ

mình.

Ta thấy A0 và A58 là một cặp.
Định lý 2. Cho đồ thị G  (V , E) ta có kết quả
4


 (d (x)  d ( y))   d

xyE

2

(v )

vV

Trong đó kí hiệu d ( x ) là bậc của đỉnh x .
Chứng minh. Ta sử dụng kĩ thuật đếm bằng hai cách
Ta đếm số bộ (u , x , v ) thỏa mãn hai cạnh u và v có chung đỉnh x .
Nếu đếm theo x thì kết quả là d 2 ( x) .
Nếu đếm theo cạnh u  xy thì kết quả là d ( x )  d ( y ) .
Do đó:

 (d (x)  d ( y))   d

xyE

2


(v )

vV

2. Đồ thị đầy đủ, đồ thị hai phần
Định nghĩa 1. Cho G  ( E , V ) là một đồ thị hữu hạn. Đồ thị G được gọi là đầy đủ nếu mọi
cặp định của nó đều được nối bởi một đỉnh. Một đồ thị đầy đủ trên n đỉnh được gọi là K n .

Đồ thị

Nhận xét: Đồ thị K n có

K7

n(n  1)
cạnh.
2

Định nghĩa 2. Cho G  (V , E ) là một đồ thị. Đồ thị bù G của đồ thị G là một đồ thị có cùng
tập hợp các đỉnh với G , còn tập cạnh là E (G )  {e  E (G )} . Cạnh của G là các cạnh không
thuộc G .

5


Định nghĩa 3. Một đồ thị G được gọi là hai phần nếu tập các đỉnh V (G ) có thể chia thành 2
tập không giao nhau A và B sao cho không có cạnh có đầu mút nằm trên cùng một tập.

Định nghĩa 4. Một đồ thị được gọi là hai phần đầy đủ nếu đỉnh V (G ) có thể chia thành 2 tập
không giao nhau A và B cạnh giữa A và B đều được vẽ. Trong trường hợp | A | m và

| B | n ta kí hiệu một đồ thị như thế là K m,n .
Bài toán 3. Có 2018 con gà vào 1009 cái lồng. Mỗi ngày người ta đều nhốt số gà trên vào các
lồng, sao cho mỗi lồng có đúng 2 con và hai con gà bất kì bị nhốt chung không quá một lần.
Chứng minh rằng chỉ nhốt gà được nhiều nhất 2017 ngày.

Lời giải
Xét đồ thị G gồm 2018 đỉnh ứng với 2018 con gà, hai đỉnh được nối với nhau nếu hai con
2
gà tương ứng được nhốt chung. Số cạnh của đồ thị nhiều nhất là C2018
, mà mỗi ngày có 1009
2
C2018
cạnh được vẽ. Vậy số ngày nhốt gà không vượt quá
 2017 .
1009

Bây giờ ta chỉ ra rằng có thể nhốt gà đúng 2017.
Ta đánh số các con gà từ i  1 đến 2018 .
Ngày thứ k con gà i được nhốt với con gà j nếu i  j  k
Nếu k chẵn thì ta con gà

mod 2018 .

k
k
được ghép với  1009 .
2
2

Bài toán 4. Một câu lạc bộ học nhảy có 10 ông và 10 bà. Biết rằng mỗi bà quen đúng 3 ông

và mỗi ông quen đúng 3 bà. Chứng minh rằng có thể chia 20 người này thành 10 cặp ông –
bà, mà mỗi cặp đều quen nhau.
3. Định lý Mantel – Turan
Định lý 3. (Mantel). Cho G là đồ thị n đỉnh, không chứa tam giác (không chứa K3 ) thì số

 n2 
cạnh lớn nhất của G là   .
4
6


Chứng minh
Vì đồ thị không chứa tam giác nên với một cạnh xy  E .
Ta thấy hai đỉnh x, y không thể cùng được nối với một trong n  2 đỉnh còn lại.
Nên d ( x )  1  d ( y )  2  n  2 hay d ( x )  d ( y )  n .
Suy ra

 d ( x)  d ( y )  n | E |
xyE

  d 2 ( v)  n | E | .
vV

Áp dụng bất đẳng thức Cauchy – Schwarz ta có:

d

2

(v ) 


vV

1
1
( d (v)) 2  .4 | E |2 .
n vV
n

1
n2  n 2 
Suy ra n | E | 4 | E |2 | E |
  .
n
4 4

Bây giờ ta chỉ ra có một đồ thị có


mà không có tam giác.

Nếu n chẵn thì G là một đồ thị 2 phần đầy đủ, mỗi phần có

n
đỉnh nói cách khác G là
2

một K n n .
,
2 2




Nếu n thì G là một đồ thị 2 phần đầy đủ, một phần có

n 1
đỉnh và một phần có
2

n 1
đỉnh nói cách khác G là một K n1 n1 .
,
2
2 2
Định lý 4. (Turan). Đồ thị G là có n đỉnh và k - tự do, số cạnh lớn nhất của đồ thị

k  2 n2
. .
k 1 2

Chứng minh
Cách 1. Ta chứng minh bằng quy nạp. Với n  1,2,3 mệnh đề đúng.
Giả sử mệnh đề đúng tới n 1, với n  4 . Ta chứng minh mệnh đề đúng với n .
Giả sử đồ thị G không chứa K k nhưng chứa K k1 vì nếu không chứa ta có thể bổ sung thêm
cạnh.
Lấy một K k1 trong G , bỏ K k1 trong G ta được đồ thị G ' với n  k  1 đỉnh, theo giả thiết
quy nạp ta có, số cạnh của G ' tối đa là

k  2 (n  k  1)2
.

.
k 1
2
7


2
Số cạnh của K k1 là Ck1


(k  1)(k  2)
.
2

Một đỉnh của G ' chỉ được phép nối với nhiều nhất k  2 đỉnh trong K k1 vì nếu nối nhiều
hơn thì sẽ tạo ra K k . Nên số cạnh nối giữa G ' và K k1 tối đa là (n  k  1)(k  2) .
Suy ra số cạnh tối đa của G là

k  2 (n  k 1)2 (k  1)(k  2)
k  2 n2
.

 (n  k  1)(k  2) 
. .
k 1
2
2
k 1 4

Bài toán 5. Một nhóm 6 người, cứ 3 người bất kì thì có 2 người không quen nhau. Hỏi có ít

nhất bao nhiêu cắp không quen nhau?

Lời giải
6 người là 6 đỉnh của một đồ thị, 2 đỉnh được nối với nhau nếu 2 người đó quen nhau.
Theo giả thiết đồ thị này không có tam giác. Nên theo định lý Mantel số cạnh nhiều nhất
62
 9.
bằng
4
Vậy số cắp không quen ít nhất là C62  9  6 .
Bài toán 6. Một nhóm 11 người chơi cờ tại một thời điểm, cứ 3 người thì có 2 người chưa
đấu với nhau. Chứng minh thời điểm này có nhiều nhất bao nhiêu trận đấu đã xảy ra?

Lời giải
Xét đồ thị G có 11 đỉnh ứng với 11 kì thủ. Hai đỉnh được nối với nhau nếu hai kì thủ đã đấu
với nhau.
Theo đề bài thì trong đồ thị không có tam giác nên theo định lý Mantel thì số trận đấu là

Bài toán 7. [MOSP 2011]. Cho S  {x1 , x2 ,, xn } là có n số thực. Hai số thực phân biệt xi , x j
được gọi là một cặp “tốt” nếu 1 <| xi  x j |< 2 . Chứng minh rằng có không quá

n2
cặp tốt.
4

Lời giải
Mặc dù đề bài phát biểu giống một bài toán đại số hơn nhưng đáp số

n2
giúp ta liên tưởng

4

đến định lý Mantel.
Xét đồ thị G có n đỉnh ứng với n phần tử của tập S , hai đỉnh ứng với xi và x j được nối
với nhau nếu 1 <| xi  x j |< 2 . Ta chứng minh trong G không có tam giác.
8


Thật vậy giả sử có 3 số thực xi , x j , xk cùng thỏa mãn

1 <| xi  x j |< 2
1 <| x j  xk |< 2
1 <| xk  xi |< 2
Không mất tính tổng quát giả sử xi < x j < xk .
Khi đó | xk  xi | xk  xi  xk  x j  x j  xi | xk  x j |  | x j  xi | 1 1  2 . Vô lý.
Theo định lý Mantel số cặp tốt không quá

n2
.
4

Bài toán 8. Trên mặt phẳng cho n điểm phân biệt. Gọi T (n) là số đoạn thẳng có độ dài bằng
1 được lập từ các điểm này. Chứng minh T (n) 

n2
.
3

Lời giải
Ta chứng minh trong đồ thị không có K 4 bằng phản chứng.

Giả sử trong đồ thị có K 4 ứng với 4 điểm ABCD .
Khi đó  ABC , BCD là các tam giác đều nên AD  3 . Vô lý.

4  2 n2 n2
Vậy theo định lý Turan ta có T (n) 
.  .
4 1 2
3
Bài toán 9. (VMO 2017). Cho số nguyên n  1 . Bảng vuông ABCD  kích thước n  n gồm
n 2 ô vuông đơn vị , mỗi ô vuông đơn vị được tô bởi ba màu : đen, trắng, xám . Một cách tô
màu được gọi là đối xứng nếu mỗi ô có tâm trên đường chéo AC được tô màu xám và mỗi
cặp ô đối xứng qua AC được tô màu đen hoặc cùng màu trắng. Người ta điền vào mỗi ô
xám số 0 , mỗi ô trắng một số nguyên dương và mỗi ô đen một số nguyên âm . Một cách
điền số như vậy được gọi là k  cân đối (với k là số nguyên dương) nếu thỏa mãn các điều
kiện sau:
9


(i) Mỗi cặp ô đối xứng qua AC được điền cùng một số nguyên thuộc đoạn  k ; k  .
(ii) Nếu một hàng và một cột giao nhau tại ô đen thì tập các số nguyên dương được điền
trên hàng đó và tập số nguyên dương được điền trên cột đó không giao nhau;nếu một hàng
và một cột giao nhau tại ô trắng thì tập các số nguyên âm được điền trên hàng đó và tập các
số nguyên âm được điền trên cột đó không giao nhau.
a)Với n  5 , tìm giá trị nhỏ nhất của k để tồn tại cách điền hình số k  cân đối cho cách tô
màu như hình bên dưới.

b)Với n  2017 , tìm giá trị nhỏ nhất của k để với mọi cách tô màu đối xứng , luôn tồn tại
cách điền k cân đối.

Lời giải

Bước 1: Xét một cách tô màu đối xứng bất kì của bảng n  n thành một đồ thị n đỉnh như
sau. Trước hết ta đánh số các hàng của bảng từ trên xuống dưới và đánh số các cột của
bảng từ trái sang phải theo thứ tự từ 1 đến n . Ô ở vị trí giao của hàng thứ i và cột thứ j gọi
là ô (i; j ) . Xét đồ thị G có n đỉnh v1 vn trong đó đỉnh vi ứng với hàng thứ i . Đỉnh vi được
nối với đỉnh v j nếu ô (i; j ) được tô màu trắng.
Nhận xét 1:



Đường chéo được tô màu xám giúp đồ thị không có khuyên;
Cách tô màu đối xứng, tứ là hai ô (i; j ) và ( j; i ) giống nhau nên đồ thị là vô hướng.

Bước 2: Việc điền số trên bảng trở thành việc đánh số các cạnh của đồ thị như sau:


Trên đồ thị G ta dùng các số nguyên dương từ 1 đến k để đánh số các cạnh của đồ
thị (hai cạnh khác nhau có thể đánh chung bằng một số). Ta kí hiệu s (v) là tập các số
dùng để đánh số các cạnh có đầu mút là đỉnh v . Việc đánh số các cạnh phải thỏa mãn
nếu u và v là 2 đỉnh không kề nhau thì s (u )  s (v)   .



Trên đồ thị G , người ta dùng các số nguyên âm từ k đến 1 để đánh số các cạnh
của đồ thị (hai cạnh khác nhau có thể đánh chung bằng một số). Ta kí hiệu s (v) là
10


tập các số dùng để đánh số các cạnh có đầu mút là đỉnh v . Việc đánh số các cạnh phải
thỏa mãn nếu u và v là 2 đỉnh không kề nhau thì s (u )  s (v)   .
Nhận xét 2: Nếu có một đồ thị con đầy đủ trong G thì ta chỉ cần dùng một số để đánh số

cho tất cả các cạnh của đồ thị con đó.
Sau khi chuyển sang ngôn ngữ đồ thị bài toán trở thàn như sau:
a) Cách tô màu ở bảng đã cho trở thành một đồ thị 5 đỉnh như sau:

Đồ thị G


Đồ thị G

Xét trên G ta dùng số 1 để đánh số ba cạnh của tam giác v1v2 v5 , ta phải dùng số 2
để đánh số ba cạnh của tam giác v2 v3v4 vì v1 , v3 không kề nhau. Ta phải dùng số 3 để
đánh số nốt cạnh cuối cùng v4 v5 vì v4 không kề v1 và v5 không kề v3 .



Trên đồ thì G ta dùng số 1 để đánh cho cạnh v1v4 . Do v3 không kề v4 ta phải dùng
số 2 để đánh cạnh v1v3 , v5 không kề với cả v1 và v2 nên ta phải dùng số 3 để đánh
cho cạnh v3v5 .

Vậy đáp án của ý a) là k  3 .
Nhận xét 4: Rõ ràng việc chuyển bài toán về ngôn ngữ đồ thị
b) Nhận xét 3:
Nếu với một số k mà ta đánh số được các cạnh mọi đồ thị G có n đỉnh thì, do G cũng có n
đỉnh như G , nên ta cũng đánh số được cho các cạnh của G . Vì vậy ta chỉ cần giải bài toán
đánh số các cạnh trên đồ thị G là đủ.
Ta giải bài toán tổng quát.
Bài toán. Chứng minh rằng số k nhỏ nhất để có thể đánh số các cạnh cho mọi đồ thị có n
 n2 
đỉnh là   .
4

Ta chứng minh bằng quy nạp.
Với n  1, 2,3 dễ dàng thấy mệnh đề đúng.
Giả sử mệnh đề đúng tới n với n  3 . Ta chứng minh mệnh đề đúng với n  1. .
11


 (n  1) 2 
TH1: Nếu đồ thị không chứa tam giác thì theo định lý Mantel đồ thị có tối đa 
 . Ta
 4 
 (n  1) 2 
đánh số các cạnh bằng các số nguyên phân biệt thì dùng hết tối đa 
 số.
 4 
TH2: Nếu đồ thị chứa tam giác. Giả sử 3 đỉnh của tam giác là u, v, w  . Vì 3 đỉnh này kề nhau
nên ta dùng một số để đánh số cho cả 3 cạnh uv, vw, wu  . Các cạnh còn lại nối với 3 đỉnh
này dùng hết nhiều nhất nhiều nhất n  1  3  n  2 số nữa.
Xóa 3 đỉnh u, v, w  đi thì đồ thị còn lại n  2 , theo giả thiết quy nạp, ta phải dùng nhiều nhất

 (n  2) 2 
là 
.
 4 
Vậy dùng hết nhiều nhất là 1  n  2 

(n  2) 2 n 2 (n  1) 2

<
.
4

4
4

 n2 
Bây giờ ta phải chỉ ra một đồ thị có n đỉnh mà phải dùng hết đúng   .
4
Giống như chứng minh định lý Mantel.
Nếu n chẵn, ta xét một đồ thị 2 phần đầy đủ K n n .
,
2 2

Nếu n lẻ, ta xét một đồ thị 2 phần đầy đủ K n 1 n 1 .
2

,

2

 n2 
Đồ thị này có   cạnh và không chứa một tam giác nào nên các cạnh phải đánh số khác
4
nhau.
Bài toán 10. Một đồ thị có 2n đỉnh và có nhiều hơn n 2 cạnh, chứng minh rằng nó có nhất n
tam giác.

Lời giải
Với n  2 , bài toán đúng.
Giả sử mệnh đề đúng với n  2 . Ta chứng minh mệnh đề đúng với n  1 .
Thật vậy xét đồ thị G có 2n  2 đỉnh và có n 2  2n  2 cạnh.
Kí hiệu t (G ) là số tam giác trong đồ thị G .

Gọi cạnh e  uv là cạnh mà d (u )  d (v)  2 nhỏ nhất và gọi giá trị đó là m .

12


TH1: m  2n thì e phải là cạnh của một tam giác. Do cách chọn m là nhỏ nhất nên tất cả các
cạnh của đồ thị đều là cạnh của một tam giác.
Do vậy ta có 3t (G )  n 2  2n  2  3n  3 nên t (G )  n  1.
TH2: m  2n . Xóa 2 đỉnh u, v và các cạnh nối với chúng. Ta được một đồ thị G1 có 2n đỉnh
và n 2  1 cạnh. Theo giả thiết quy nạp t (G )  t (G1 )  n .
Gọi tập các đỉnh kề với u là U1 , các đỉnh kề với v là V1 .
Nếu U1 ,V1 có ít nhất một đỉnh chung thì ta có thêm ít nhất 1 tam giác nữa.
Nếu U1 ,V1 không có đỉnh chung thì mỗi đỉnh của G1 được nối với đúng một trong 2 đỉnh u
hoặc v .
Xét một tam giác tong G1 , tam giác này phải có 2 đỉnh cùng nằm trong U1 hoặc V1 . Giả có
đỉnh nằm trong U1 thì 2 đỉnh này cùng với u lập thành một tam giác nữa.
TH3: Nếu m < 2n . Ta xóa u, v khỏi đồ thị và cạnh nối với chúng. Ta được đồ thị G1 có 2n
đỉnh và có ít nhất n 2  2 cạnh. Theo giả thiết quy nạp G1 chứa tam giác. Xóa một cạnh của
tam giác. Ta được đồ thị G2 có 2n đỉnh và có ít nhất n 2  1 cạnh. Theo giả thiết quy nạp. G2
có ít nhất n tam giác. Nên G1 có ít nhất n  1 tam giác.
4. Một số bài tập tự luyện
Bài toán 11. (China TST, 1987) Trong mặt phẳng có 2n điểm với n  2 và có tất cả n 2  1
đoạn thẳng nối chúng. Giả sử không có 3 điểm nào thẳng hàng, chứng minh rằng:
a) Tồn tại ít nhất một tam giác;
b) Tồn tại hai tam giác có cạnh chung;
c) Tồn tại ít nhất n tam giác.
Bài toán 12. (Romania TST 2008) Cho số nguyên dương n  1 . Xét một nhóm người thỏa
mãn đặc điểm sau:
i) Trong 3 người bất kì luôn tồn tại hai người quen biết nhau;
ii) Trong n người bất kì luôn tồn tại hai người không quen biết nhau.

Chứng minh số lượng người không quá

(n  1)(n  2)
.
2

Bài toán 13. (USA TST 2008) Với mỗi cặp điểm A( x1 , y1 ) và B( x2 , y2 ) trong mặt phẳng
Oxy  ta đặt d ( A, B) | x1  xx |  | y1  y2 |

Ta gọi cặp ( A, B) (không tính thứ tự) là điều hòa nếu 1 < d ( A, B) < 2 . Xác định số cặp hiều
hòa lớn nhất trong 100 điểm trong mặt phẳng.
13


TÀI LIỆU THAM KHẢO
[1]. Vũ Đình Hòa, Một số kiến thức cơ sở về grahp hữu hạn, NXB Giáo dục, 2006.
[2]. J. H. van Lint và R. M. Wilson, A Course in Combinatorics, Cambridge University
Press 2001.
[3]. Trần Minh Hiền, Định lý Turan, Kỷ yếu các phương pháp giải toán qua các kỳ thi
olympic, TP. Hồ Chí Minh, 2014.
[4]. Adrian Tang, IMO Training 2008: Graph Theory.

14