1. Hoán vị:
Nếu sắp xếp vật khác nhau theo một thứ tự nào đó thì sẽ có n cách chọn vật thứ nhất, n - 1 cách chọn vật thứ hai, .. , 1 cách chọn vật cuối cùng. Do đó, có:
n(n – 1)(n – 2)…3.2.1 cách sắp xếp khác nhau.
Số này được kí hiệu là n! và được gọi là n giai thừa.
Mỗi cách sắp xếp khác nhau gọi là một hoán vị, và số hoán vị của n vật được kí hiệu là Pn. Do đó:
Pn = n!
Ví dụ: Có 6! = 720 cách sắp xếp đội hình của một đội bóng chuyền 6 người.
2. Hoán vị lặp không hạn chế:
Nếu muốn sắp xếp n vật từ k loại vật khác nhau (các vật cùng loại giống hệt như nhau) thì sẽ có k cách chọn vật thứ nhất, k cách chọn vật thứ hai,… , k cách chọn vật thứ n. Do đó có kn cách khác nhau.
Ví dụ: có 83 số có 3 chữ số không chứa chữ số 0 hay 9.
3. Hoán vị lặp hạn chế:
Có k loại vật khác nhau, loại 1 có n1 vật, loại 2 có n2 vật,…, loại k có nk vât; và tồng số vật sẽ là n (= n1 + n2 + … + nk). Nếu coi n vật này là khác nhau thì sẽ có n! cách sắp xếp, nhưng trong mỗi cách sắp xếp như vậy n1 phần tử loại 1 có thể hoán vị theo n1! cách, n2 phần tử loại 2 có thể hoán vị theo n2! cách, … , nk phần tử loại k có thể hoán vị theo nk! cách. Do đó, số cách sắp xếp chỉ còn
____n!____
n1!n2!.......nk!
Ví dụ: Số các “chữ” khác nhau có thể có được bằng cách dùng các con chữ của chữ “Mississippi” là:
11!4!4!2!1!=34 650
4. Chỉnh hợp k vật từ n vật ( k ≤ n):
Nếu sắp xếp k vật (được chọn từ n vật) theo một thứ tự nào đó (không được lặp lại) thì sẽ có n cách chọn vật thứ nhất, n -1 cách chọn vật thứ hai, … , n – k +1 cách chọn vật thứ k. Do đó số cách sắp xếp k vật từ n vật là
n(n – 1)…(n – k + 1) = n! / (n – k)!
Số này được kí hiệu là Akn, An,k, A(n,k)... Do đó:
A(n,k) = n! / (n – k)!
Chỉnh hợp lặp k vật từ n vật ( k ≤ n): Nếu cho phép lặp lại thì sẽ có nk cách sắp xếp k vật từ n vật.
Hoán vị (hoán vị lặp không hạn chế) là trường hợp đặc biệt của chỉnh hợp (chỉnh hợp lặp) khi k = n.
Ví dụ 1: Có 20 = 5×4 (= 5!/(5-2)!) cách chọn 2 bạn làm lớp trưởng và lớp phó từ một danh sách đề cử gồm 5 bạn.
Ví dụ 2: Có 2n – 2 số có n chữ số được tạo thành từ 2 chữ số 1 và 2 và có chứa cả 2 chữ số này.
5. Tập con k phần tử từ tập n phần tử ( k ≤ n):
Theo mục 4. có n!/(n – k)! cách chọn k phần tử có thứ tự từ n phần tử, nhưng mỗi cách chọn này có thể hoán vị theo k! cách, vì thế k! cách sắp xếp khác nhau này chỉ trên các phần tử của cùng một tập con k phần tử. Do đó, có
__n!__
(n-k)! k!
tập con k phần tử từ tập n phần tử.
Số này có kí hiệu là C(n,k), Cn,k, Ckn , nCk, ( nk )… (đọc là “n chọn k”). Một tập con k phần tử gọi là một tổ hợp (ở đây dùng C(n, k) để tiện việc trình bày).
C(n,k) = n! / (n - k)!k!
Tính chất của C(n,k)
(i) C(n,0) = C(n,n) = 1 và C(n,1) = n.
(ii) C(n,k) = C(n,n – k). Cả hai đều bằng n!/(k!(n – k)!).
(ìii) C(n,k)/n = C(n – 1,k – 1)/k.
(iv) C(n+1,k+1) = C(n,k+1) + C(n,k). Có thể kiểm chứng điều này không khó từ công thức của tổ hợp. Đây là công thức dùng khi lập tam giác Pascal (số ở hàng n+1, cột k+1 là tổng của số ở hàng n,cột k và số ở hàng n, cột k+1).
*Tam giác Pascal:
n \ k
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
…
|
0
|
1
|
|
|
|
|
|
|
|
|
|
1
|
1
|
1
|
|
|
|
|
|
|
|
|
2
|
1
|
2
|
1
|
|
|
|
|
|
|
|
3
|
1
|
3
|
3
|
1
|
|
|
|
|
|
|
4
|
1
|
4
|
6
|
4
|
1
|
|
|
|
|
|
5
|
1
|
5
|
10
|
10
|
5
|
1
|
|
|
|
|
6
|
1
|
6
|
15
|
20
|
15
|
6
|
1
|
|
|
|
7
|
1
|
7
|
21
|
35
|
35
|
21
|
7
|
1
|
|
|
8
|
1
|
8
|
28
|
56
|
70
|
56
|
28
|
8
|
1
|
|
…
|
|
|
|
|
|
|
|
|
|
|
Trong tam giác trên, số 15 = C(6,4) (trên nền lục ở hàng 6, cột 4) là tổng của số 10 = C(5,3) (trên nền cam ở hàng 5, cột 3) và số 5 = C(5,4) (trên nền cam ở hàng 5, cột 4): 15 = 10 + 5
(v) C(n,k) là hệ số của xkyn-k trong biểu thức khai triển của (x + y)n nên còn được gọi là hệ số nhị thức (binomial coefficent).
( x + y)n = C(n,0) xny0 + C(n,1)xn - 1y1 + C(n,2)xn - 2y2 + . . . + C(n,n)x0yn.
(vi) 2n = C(n,0) + C(n,1) + C(n,2) + + C(n,n). (cho x = y = 1 trong công thức khai triển nhị thức trong mục (v))
0 = C(n,0) – C(n,1) + C(n,2) - … + (-1)kC(n,k) + + (-1)nC(n,n). (cho x = 1, y = -1 trong công thức khai triển nhị thức trong mục (v)).
Kết quả đầu cho thấy một tập n phần tử có tất cả 2n tập con vì nó có C(n,0) tập con 0 phần tử, C(n,1) tập con 1 phần tử,…, C(n,k) tập con có k phần tử,…, C(n,n) tập con có n phần tử.
(vii m=1nC(m,k) = C(k,k) + C(k+1,k) +… + C(n,k) = C(n+1,k+1).
Trong tam giác Pascal trên số 35= C(7,3) trên nền vàng là tổng các số trên nền lam [C(2,2), C(3,2), C(4,2), C(5,2), C(6,2), C(7,2)]:
35 = 1 + 3 + 6 + 10 + 15.
m=0k C(n - k +i,i) = C(n-k,0) + C(n-k+1,1) +… + C(n,k) = C(n + 1,k).
Trong tam giác Pascal trên số 28 = C(8,2) màu đỏ bằng tổng của các số màu lam [1=C(5,0), 6 =C(6,1), 21=C(7,2)]: 28 = 1 + 6 + 21.
(viii) r=1n-1 r(n-r) = 1(n – 1) + 2(n – 2) + … + (n – 1)1 = C(n+1,r).
6. Tổ hợp lặp:
Giả sử có một tập k phần tử gồm k1 phần tử thuộc loại 1, k2 phần tử thuộc loại 2, … , km phần tử thuộc loại m (k1 + k2 + … + km = k, m ≤ k). Tập hợp này có thể biểu diễn trên đường thẳng bằng k điểm ngăn cách bởi m – 1 dấu | (để phân cách các phần tử khác loại nhau): bắt đầu bằng k1 điểm (biểu thị các phần tử loại 1) đi theo bởi 1 dấu |, kế đến k2 điểm (biểu thị các phần tử loại 2) đi theo bởi 1 dấu |, …., rồi sau cùng là km điểm (biểu thị các phần tử loại m). Có thể có một vài k = 0 nên có thể cũng sẽ xảy ra trường hợp một số dấu | đi liền với nhau.
• • • •…• • | • • • •…• | • …… | • • •…• •
k1 điểm k2 điểm …… km điểm
Những cách chọn khác nhau tập k phần tử sẽ cho ra các cách sắp xếp khác nhau k điểm và m – 1 dấu | trên đường thẳng. Do đó số các tập k phần tử thuộc nhiều nhất m loại khác nhau (m ≤ k) sẽ bằng số cách sắp xếp k + m -1 phần tử trong đó k phần tử cùng một loại và m – 1 phần tử thuộc loại khác. Theo mục 3. số này bằng:
(k + m – 1)!/(k!(m-1)!) hay bằng C(k + m – 1, k).
Ví dụ: Số cách để mua 7 li cà phê từ một của hàng có bán cà phê phin, cà phê đá, cà phê sữa và cà phê sữa đá là C(10,7) = C(10,3) =120.
7. Nguyên tắc Hàm chứa - Loại trừ (Inclusion – Exclusion):
Giả sử có n vật mà mỗi vật có thể có nhiều nhất k tính chất P1, P2, … , Pk. Gọi N(Pi, Pj,…, Pq) là số vật có các tính chất Pi, Pj, … và Pq (và có thể cũng có những tính chất khác) thì só các vật không có tính chất nào là:
n – [N(P1) + N(P2)+ … + N(Pk)]
+ [N(P1,P2) + N(P1,P3)+ …..+ N(Pk-1,Pk)]
– [N(P1,P2,P3) + N(P1,P2,P4) +…+ N(Pk-2,Pk-1,Pk)]
+ …
+ (-1)k N(P1,P2,…,Pk)
trong đó mọi tổ hợp của P1, P2,… , Pk đều xuất hiện với dấu + nếu số tính chât là chẵn và với dấu - nếu số tính chất là lẻ.
Số này sẽ là n - [N(P1) + N(P2)] - N(P1,P2) trong trường hợp k=2.
Ví dụ 1: Trong một lớp học gồm 45 học sinh có 25 học tiếng Anh, 23 học tiếng Pháp và 20 học cả Anh và Pháp. Số học sinh trong lớp không học ngoại ngữ nào là:
45 – (25+ 23) + 20 = 17
Ở đây n = 45, k =2, P1= học tiếng Anh, P2 = học tiếng Pháp.
Ví dụ 2: Tìm số các số tự nhiên k với 1 ≤ k ≤ 1988 nguyên tố cùng nhau với 1988. Ở đây n = 1988. Vì 1988 = 22 × 7 × 71 nên có 3 tính chất cần quan tâm tới: P1 = chia hết cho 2, P2= chia hết cho 7 và P3 = chia hết cho 71. Ta có
N(P1) = 1988/2 = 994, N(P2) = 1988/7 = 284 và N(P3) = 1988/71 = 28.
Có cả tính chất P1 và P2 có nghĩa là phải chia hết cho 2 × 7 = 14, nên N(P1,P2) =1988/14 = 142,
Tương tự: N(P1,P3) = 1988/142 = 14, N(P2,P3) = 1988/497 = 4 và N(P1,P2,P3)=1988/994 = 2.
Do đó số các số k không chia hết cho 2,7 lẫn 71 bằng
1988 – (994 + 284 + 28) – (142 + 14 + 4) – 2 = 840.
8. Nguyên tắc ô chuồng bồ câu / Nguyên tắc Diretchlet (Pigeon-hole Principle):
Đặt N vật vào k ô, nếu N > k thì thì ít nhất có một ô chứa ít nhất 2 vật. Tổng quát hơn, Nếu n > km thì có ít ra một ô chứa ít nhất m + 1 vật. (vì nếu mỗi ô chỉ chứa nhiều nhất m vật thì k ô chỉ chứa tối đa km vật thôi).
Nguyên tắc này còn được gọi phát biểu dưới dạng: Nhốt N thỏ vào k lồng và nếu N > k thì có ít nhất một lồng chứa hơn 1 con thỏ.
Dễ thấy tính đúng đắn của nguyên tắc này qua phản chứng.
Ví dụ: Trong một buổi họp mặt có 6 người thì sẽ có một bộ ba người hoặc đều đã quen nhau cả hoặc chưa hề biết nhau. (Ta giả định nếu X quen Y thì tự động Y cũng quen với X). Gọi A là một trong những người trong buổi hop mặt đó, và phân 5 người còn lại thành 2 lớp: biết A và không biết A. Theo nguyên tắc ô bồ câu, do 5 > 2 × 2 nên một trong hai lớp đó phải có ít nhất 3 người. Giả sử lớp có ít nhất 3 người là lớp không biết A, xét bất kì nhóm 3 người trong lớp đó, nếu có một cặp 2 người nào đó không quen biết nhau, đem gộp với A với cặp này ta sẽ được nhóm 3 người không quen nhau. Nếu không có cặp 2 người nào không quen nhau (ie bất kì cặp 2 người trong nhóm 3 người đều quen nhau) tất nhiên cả nhóm 3 người này đều quen nhau. Lí luận tương tự cho trường hợp lớp có ít nhất là lớp quen với A.
9. Đếm theo 2 cách:
Một kĩ thuật đắc dụng trong các bài toán tổ hợp là đếm các vật theo 2 cách để hình thành một phương trình hay một đẳng thức.
Ví dụ 1: Nếu một khối đa diện có tất cả các mặt là tam giác và mỗi đỉnh đều là điểm chung của 3 cạnh thì số mặt và số đỉnh của nó bằng nhau và hơn nữa là một số chẵn.
Thật vậy, gọi V là số đỉnh, E là số cạnh và F là số mặt của khối đa diện, và đếm số cạnh bằng cách xem mỗi cạnh là phần giao của 2 mặt mà mỗi mặt lại có 3 cạnh nên 3F = 2E (3F là tổng số cạnh của F mặt tách rời, nhưng mỗi cạnh của khối đa diện là phần chung của 2 mặt nên đếm như thế tức là đếm mỗi cạnh của khối đa diện 2 lần nên cũng bằng 2E). Bây giờ đếm số cạnh bằng cách để ý rằng mỗi cạnh chứa 2 đỉnh và mội đỉnh là điểm chung của 3 cạnh nên 3V = 2E. Do đó F = V, hơn nữa vì 3F = 2E là số chẵn mà 3 là số lẽ nên F phải chẵn.
Ví dụ 2: Nếu tổng của 9 số tự nhiên a1, a2, a3, a4, a5, a6, a7, a8, a9 là 90 thì sẽ có ít nhất 4 trong các số đó có tổng ít nhất bằng 40.
Thật vậy chỉ cần viết các số này theo cách sau đây:
a1 a2 a3 . . . a9
a2 a3 a4 . . . a1
a3 a4 a5 . . . a2
a4 ạ5 a6 . . . a3
Để ý rằng tổng của mỗi hàng là 90 nên tổng của toàn bảng là 90 × 4 = 360. Bây giờ xét tổng của các cột. Có tất cả 9 cột, vì thế phải có ít ra một cột có tổng lớn hơn hoặc bằng 360/9 = 40.
10. Quy nạp toán học:
Giả sử bạn được yêu cầu tìm một công thức tổng quát cho tổng của n số lẻ đầu tiên. Bạn có thể sẽ bắt đầu bằng cách xem xét một vài trường hợp đặc biệt:
1 = 1
1+3 = 4
1 + 3 + 5 = 9
1 + 3 + 5 + 7 = 16
Từ đó bạn có thể sẽ phỏng đoán ra công thức
1 + 3 + 5 + . . . + (2n – 1) = n².
Dĩ nhiên, 4 trường hợp đặc biệt này không chứng minh rằng công thức trên là đúng mà chỉ làm cho nó có vẻ có lí thôi. Phương pháp dễ dàng nhất để có một chứng minh thuyết phục rằng công thức trên đúng cho mọi n là dùng quy nạp toán học. Đây là phương pháp để chứng minh rằng một điều gì đó là đúng cho mọi số tự nhiên. Bạn có một mệnh đề S(n) nào đó về số tự nhiên n mà bạn muốn chứng minh mệnh đề đó đúng cho mọi số tự nhiên n. Nguyên lí của Quy nạp toán học như sau:
Giả sử ta có thể chứng tỏ
(i) S(1) là đúng, và
(ii) cho số tự nhiên tổng quát k, nếu S(k) là đúng thì S(k + 1) cũng phải đúng
Khi đó, có thể kết luận S(n) đúng với mọi n.
Bởi vì với 2 điều trên ta có thể xác lập tính đúng đắn của mọi mệnh đề S(n) với n là số tự nhiên: trước hết, ta có S(1) đúng theo (i); Kế đến vì S(1) đã đúng nên theo (ii) S(2) phải đúng; rồi do S(2) đã đúng nên lại theo (ii) S(3) phải đúng; và cứ thế tiếp tục lập luận tương tự tới vô hạn.
Ví dụ: Chứng minh công thức mà chúng ta vừa dự đoán ở trên. Như thế ở đây S(n) là mệnh đề 1 + 3 + … + (2n – 1) = n².
Ta có S(1) là 1 = 1² rõ ràng là đúng.
Bây giờ giả sử với một số k tổng quát S(k) là đúng, tức là 1 + 3 + … + (2k – 1) = k². (gọi là giả thuyết quy nạp) ta phải chứng tỏ rằng S(k+1) sẽ đúng.tức là 1 + 3 + … + (2k – 1) + [(2(k+1) – 1] = (k +1 )².
Thật vậy, ta có:
1 + 3 + … + (2k – 1) + (2k + 1) = [1 + 3 + … + (2k – 1)] + (2k + 1)
= k². + (2k + 1) (theo giả thuyết quy nạp)
= (k + 1)²
Do đó, theo quy nạp S(n) đúng với mọi n.
Nguyên tắc Quy nạp toán học có một số biến thái:
Quy nạp với 2 trường hợp gốc:
(i) S(1) và S(2) là đúng, và
(ii) Cho số tự nhiên tổng quát k, nếu S(k) và S(k+1) đúng thì S(k+2) cũng phải đúng
Khi đó S(n) sẽ đúng với mọi n;
Quy nạp hoàn chỉnh (complete induction):
(i) S(1) là đúng, và
(ii) Cho số tự nhiên tổng quát k, nếu tất cả các mệnh đề S(1), S(2), . . . , S(k) đều đúng thì S(k+1) cũng phải đúng
Khi đó S(n) sẽ đúng với mọi n.
Quy nạp với số đầu ≠ 1:
Trong nhiều trường hợp ta phải chứng minh mệnh đề S(n) đúng với mọi n ≥ a, với a=0 hay a >1, khi đó ta chỉ cần thay S(1) [ S(2)] trong (i) bằng S(a) [S(a+1)].
Ví dụ 1: Dùng quy nạp để chứng minh rằng một đa giác n cạnh thì có n(n – 3)/2 đường chéo.
Thật vậy mệnh đề đúng khi n = 3 vì tam giác không có đường chéo nào : 0 = 3(3 -3)/2.
Bây giờ giả sử mệnh đề đúng với số k ≥ 3 tức là mỗi đa giác k cạnh có k(k – 3)/2 đường chéo.
Coi đa giác (k+1) cạnh A1A2A3 A4….Ak+1, lưu ý rằng các đường chéo của đa giác này gồm các đường chéo phát xuất từ đỉnh Ak+1, (có k+1 -3 = k – 2 đường chéo: Ak+1 nối với k – 2 đỉnh không kề liền với nó) cùng với các đường chéo của đa giác A1A2A3 A4….Ak (theo giả thuyết quy nạp có k(k-3)/2 đường chéo) và đường chéo A1Ak Do đó, số đường chéo của đa giác (k+1) cạnh A1A2A3 A4….Ak+1 là
k(k-3)/2 + (k – 2) + 1 = (k² – k – 2)/2 = (k+1) (k – 2) /2 = (k+1)[(k+1) – 3]/2.
Tức là mệnh đề cũng đúng với k+1.
Do đó, đa giác n cạnh có n(n – 3)/2 đường chéo với mọi n ≥ 3.
Ví dụ 2: Chứng minh công thức tổng quát của số Fibonacci là
fn = [φn – (- 1/φ)n] / √5 với mọi n ≥ 0 trong đó φ = ½(V5 + 1) (tỉ số vàng ).
Trong chứng minh này ta phải xác lập tính đúng đắn của công thức khi n=0 và n=1, sau đó giả sử công thức đúng khi n = k – 1 và k rồi chứng minh công thức đúng khi n = k+1 (lưu ý theo định nghĩa fn = fn-1 + fn-2 với mọi n ≥ 2).
Ví dụ 3: Chứng minh “mọi số tự nhiên lớn hơn 1 là tích của các số nguyên tố.” Trong chứng minh này, sau khi kiểm tra trường hợp n =2, ta phải giả định mệnh đề đúng cho với mọi n ≤ k để có thể chứng minh mệnh đề đúng với n=k +1.
11. Lí thuyết đồ thị:
Đồ thị có thể xem là một tập các đỉnh (hay điểm/nút) và tập các cạnh (cung), trong đó mỗi cạnh nối liền một cặp đỉnh khác nhau. Đồ thị thể hiện trên giấy bằng cách biểu diễn mỗi đỉnh bằng một dấu chấm và mỗi cạnh bằng một đường cong / thẳng giữa 2 đỉnh mà nó nối liền.
Ví dụ
Trong biểu đồ trên, việc bố trí vị trí các đỉnh, việc vẽ các cạnh thẳng hay cong cắt nhau hay không cắt là không quan trọng. Có thể có những biểu đồ trông rất khác nhau nhưng chúng lại biểu thị cho cùng một đồ thị, chẳng hạn 2 biểu đồ cuối trong ví dụ trên.
Một đồ thị G được gọi là liên thông nếu với mỗi cặp đỉnh u, v của nó có một đường dẫn dọc theo các cạnh của G đi từ u tới v (nghĩa là có mộ chuỗi các đỉnh v1, v2, … , vm với v1=u và vm =v sao cho các cặp vi, vi+1 (với i=1, 2, …, m – 1) được nối liền bằng một cạnh). Thành phần liên thông C của đồ thị G là đồ thị con tối đại của G, nghĩa là, bất kì 2 đỉnh nào của C cũng có một đường dẫn như đã nêu và mọi đình v không thuộc C thì thì không có cạnh nào nối với bất kì đỉnh nào của C. Mỗi đỉnh của một đồ thị thì chỉ nằm trong đúng một thành phần liên thong vì thế ta thường chỉ xét đến các đồ thị liên thông mà thôi.
Ví dụ: Trong các đồ thi ở ví dụ trên chỉ có đồ thị thứ hai là không liên thông, nó có 3 thành phần liên thông: hai trong chúng là 2 đỉnh rời và thành phần thứ ba gồm 3 đỉnh còn lại với tất cả các cạnh nối.
Đồ thị cung cấp một phương pháp tiện lợi để biểu diễn những điều cốt lỏi của một tình huống. Chẳng hạn, ta muốn vạch ra một lộ trình chạy xe dọc theo tất cả con đường của một vùng (như lộ trình của một người phát thư chẳng hạn). Khi đó ta biểu thị các chỗ giao lộ bằng các đỉnh và các con đường bằng các cạnh. Nều có hai con đuờng khác nhau giữa 2 giao lộ, ta vẽ 2 cạnh khác nhau nối 2 đỉnh tương ứng. Sau đó ta sẽ lập một lộ trình đi dọc theo tất cả các con đường của đồ thị sao cho chỉ dùng mỗi cạnh một lần (để tránh phải tốn công đi lại nhiều lần trên một con đường) Một lộ trình như thế, nếu tồn tại được gọi là đường đi Euler của đồ thị.
Bài toán về đường đi Euler đơn giản và quen thuộc là bài toán vẽ liền một nét không nhắt bút lên hình một bao thư.
Vài đồ thị thông dụng
1. Đồ thị vòng Cn (cycle graph) trên n đỉnh: với các đình v1, v2, . . . , vn và các cạnh nối các đỉnh liền kề vi, vi+1 ( i=1, . . .n – 1) và cạnh nối đỉnh cuối vn đỉnh đầu v1.
Đồ thị C3 được gọi là tam giác.
2. Đồ thị đầy đủ Kn (complete graph) trên n đỉnh với các đình v1, v2, . . . , vn và với mỗi cặp đỉnh vi, vj khác nhau đều một cạnh nối chúng với nhau.
3. Đồ thi đầy đủ 2 thành phần Kmn (complete bipartite graph) trên m và n đỉnh: với các đình v1, v2, . . . , vn và w1, w2, , wm và mỗt cạnh nối mỗi cặp đỉnh vi, wj khác nhau
Trong một đồ thi, bậc của một đỉnh là số cạnh khác nhau mà nó là một đầu mút.
Ví dụ: Trong bất kì đồ thị nào, số cạnh cũng bằng phân nửa tổng số bậc của các đỉnh. Bậc của mỗi đỉnh chính là số cạnh xuất phát từ đình đó. Do đó tổng các bậc của các đỉnh chính là tổng của số cạnh xuất phát từ mỗi đỉnh. Mỗi cạnh như thế được tính 2 lần, mỗi lần cho một đỉnh mà nó nối với, Vì vậy tổng số bậc của các đỉnh gấp hai lần số cạnh.
Ví dụ: Có thể tìm ra môt nhóm 7 người trong đó mỗi người quen với đúng 3 người khác hay không?
Biểu diễn bài toán nàyn dưới dạng đồ thi: Mỗi người là một đỉnh và hai người quen nhau đưọc biểu diễn bằng một cạnh nối 2 đỉnh tương ứng. Như thế ta cần một đồ thỉ có 7 đỉnh và mỗi đỉnh có bậc là 3. Với một đồ thị như thế theo ví dụ trên số cạnh phải là ½(3 × 7) = 10 ½. Nhưng số cạnh phải là số nguyên nên không thể có một đồ thị như thế. Do đó, không thể tìm ra nhóm 7 người nào có tính chất như đã nêu.
Các bài toán đếm thường được diễn tả dưới dạng tô màu các cạnh (hay các đỉnh) của một đồ thị; ta có một đồ thị và nghĩ đến việc tô màu mỗi cạnh bằng một trong các màu đỏ, xanh, vàng, tím….Nếu việc tô màu bị một khống chế nào đó, ta muốn chứng tỏ răng sẽ có một đồ thị con nào đó là đơn sắc (các cạnh đều cùng một màu).
Ví dụ: Ví dụ ở mục 8. thuộc dạng này. Sáu người biểu thị bằng 6 đỉnh, nối hai đỉnh với nhau bằng cạnh màu đỏ nếu hai người tương ứng quen nhau, hoặc bằng cạnh màu xanh nếu họ không quen nhau. Bài toán chuyển thành: các cạnh của một đồ thị hoàn chỉnh K6 được tô với 2 màu đỏ và xanh, chứng tỏ rằng nếu trong đồ thị đó không chứa một tam giác đỏ thì phải chứa một tam giác xanh.
(viết theo một số tài liệu tham khảo)
