Bài tập Toán rời rạc
Đồ thị 1
1. Xét P (m, n) là câu ”Đồ thị đầy đủ n đỉnh K
n
có đúng m cạnh”, ở đây miền giá trị của
cả hai biến là tập số nguyên dương. Xác định giá trị chân lý của các khẳng định sau:
(a) P (2, 2) = T hay F
(b) P (3, 3) = T hay F
(c) P (4, 4) = T hay F
(d) ∃m ∀n P (n, m) = T hay F
(e) ∀n ∃m P (n, m) = T hay F
(f) ∃n P (n, 2n) = T hay F
2. Xét đồ thị G = (V, E). Ta nhắc lại rằng bậc của một đỉnh v ∈ V , ký hiệu deg(v), là số
cạnh liên thuộc với nó.
(a) Chứng minh rằng
2|E| =
∑
v∈V
deg(v)
(b) Chứng minh rằng số đỉnh bậc lẻ của G luôn là số chẵn.
(c) Giả sử D và d là bậc lớn nhất và bậc nhỏ nhất của G. Chứng minh rằng
d ≤
2|E|
|V |
≤ D.
3. Nhắc lại rằng
tô màu
đồ thị là một cách gán màu cho mỗi đỉnh của đồ thị sao cho hai
đỉnh kề nhau có màu khác nhau.
Bổ đề (Sai). Xét G là một đồ thị có bậc lớn nhất không lớn hơn k. Nếu G có một đỉnh
nhỏ hơn k, vậy G có thể tô bằng k màu.

thỏa mãn các điều kiện của giả thiết quy nạp P(n). Ta kết luận rằng G
n
có thể tô
bằng k màu.
Bây giờ, k màu của đồ thị G
n
dùng để tô mọi đỉnh của đồ thị G
n+1
trừ đỉnh v. Vì v có
bậc nhỏ hơn k, có ít hơn k màu được gán cho các đỉnh kề với v. Vậy trong số k màu có
thể, sẽ có một màu không được dùng cho các nút kề với v, và màu này có thể được gán
cho v để tô G
n+1
bằng k màu.
4. Một đồ thị có độ rộng m nếu các đỉnh có nó có thể được sắp xếp thành dãy
v
1
, v
2
, · · · , v
n
sao cho mỗi đỉnh v
i
có cạnh nối với nhiều nhất là m đỉnh đứng trước nó (Đỉnh v
j
đứng
trước v
i
nếu j < i.) Dùng quy nạp để chứng minh rằng mọi đồ thị với độ rộng nhỏ hơn
hoặc bằng m đều có thể tô bằng (m + 1) màu.

9. Chứng minh hoặc bác bỏ rằng trong mọi đồ thị với n ≥ 2 đỉnh luôn có hai đỉnh cùng
bậc.
3