Topic các định lí về lí thuyết đồ thị

[batigoal]

Chào các bạn

Lí thuyết đồ thị là một môn học thuộc lĩnh vực toán học tổ hợp rời rạc . Lí thuyết đồ thị xuất hiện nhiều trong các kì thi học sinh giỏi các cấp, có thể nói đây là một môn học có nhiều ứng dụng trong thực tiễn như các mô hình lập lịch phân công công việc, các giải pháp tối ưu hóa trong hệ thống giao thông, cách đặt các trạm thu phát tín hiệu điện thoại sao cho tốt nhất,...Đây là một môn học khó với khá nhiều bạn. Một phần vì tính tư duy trừu tượng trong đó, phần khác là rất nhiều định lí về lí thuyết đồ thị chúng ta cần phải biết. Để thuận tiện cho các anh em trong việc học tập, rèn luyện và mở mang kiến thức với Lí thuyết đồ thị, cùng với mong muốn thúc đẩy học tập tốt toán tổ hợp và đặc biệt là lí thuyết đồ thị mình xin phép lập topic này mong các bạn thành viên Mathscope mỗi ngày chúng ta ủng hộ ít nhất 1 định lí bao gồm chứng minh cho định lí ấy. Topic được lập ra còn nhằm mục đích để không chỉ chúng ta học tập, rèn luyện mà các thế hệ đàn em tiếp theo của chúng ta sẽ được kế thừa kiến thức và tiếp tục học tập, cập nhật bổ sung để có một bộ lí thuyết đầy đủ hơn các anh của chúng.

Để topic sạch ,đẹp, chuyên nghiệp mình xin đưa ra một số nội quy cho topic như sau:
NỘI QUY TOPIC

1. Đánh số thứ tự định lí (Ghi tên định lí nếu có)
Mẫu thực hiện
Định lí 1
..........
Chứng minh định lí:

Chứng minh

Định lí 2 (Mantel)
..........
Chứng minh định lí:

Chứng minh

2. Nếu định lí và chứng minh sử dụng kí hiệu mới thì bạn gửi định lí hãy giải thích kí hiệu, thuật ngữ mới đó cho bạn đọc dễ quan sát và tìm hiểu.
3.Đây là topic dành riêng cho định lí, hệ quả, bổ đề nên không post bài toán hỏi về lí thuyết đồ thị ở đây, nếu cần hỏi về bài toán nào các bạn lập topic khác.
4. Các bài gửi rác, spam sẽ bị xóa mà không báo trước

Rất mong sự ủng hộ nhiệt tình của các bạn.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[batigoal]

I. CÁC ĐỊNH NGHĨA .
- Trước khi đi đến các định lí thì sau đây là một số khái niêm cơ bản để bạn đọc nhập môn lí thuyết đồ thị .
1.1. Định nghĩa 1.
Một đơn đồ thị $G = (V, E)$ gồm một tập khác rỗng V mà các phần tử của nó gọi là các đỉnh và một tập $E$ mà các phần tử của nó gọi là các cạnh, đó là các cặp không có thứ tự của các đỉnh phân biệt.
1.2. Định nghĩa 2.
Một đa đồ thị $G = (V, E)$ gồm một tập khác rỗng V mà các phần tử của nó gọi là các đỉnh và một họ $E$ mà các phần tử của nó gọi là các cạnh, đó là các cặp không có thứ tự của các đỉnh phân biệt. Hai cạnh được gọi là cạnh bội hay song song nếu chúng cùng tương ứng với một cặp đỉnh.
1.3. Định nghĩa 3.
Một đồ thị có hướng $G = (V, E)$ gồm một tập khác rỗng V mà các phần tử của nó gọi là các đỉnh và một tập E mà các phần tử của nó gọi là các cung, đó là các cặp có thứ tự của các phần tử thuộc $V$.
1.4. Định nghĩa 4.
Một đa đồ thị có hướng $G = (V, E)$ gồm một tập khác rỗng $V$ mà các phần tử của nó gọi là các đỉnh và một họ $E$ mà các phần tử của nó gọi là các cung, đó là các cặp có thứ tự của các phần tử thuộc $V$.
1.5. Định nghĩa 5
Hai đỉnh $u$ và $v$ trong đồ thị (vô hướng) $G=(V,E)$ được gọi là liền kề nếu $(u,v) \in E$. Nếu $e = (u,v)$ thì $e$ gọi là cạnh liên thuộc với các đỉnh $u$ và $v$. Cạnh $e$ cũng được gọi là cạnh nối các đỉnh $u$ và $v$.
1.6. Định nghĩa 6
Bậc của đỉnh $v$ trong đồ thị $G=(V,E)$, ký hiệu $deg(v)$, là số các cạnh liên thuộc với nó, riêng khuyên tại một đỉnh được tính hai lần cho bậc của nó.
Đỉnh $v$ được gọi là đỉnh treo nếu $deg(v)=1$ và được gọi là đỉnh cô lập nếu $deg(v)=0$.

1.7. Định nghĩa 7
Cho $A, B$ là 2 đỉnh của một đồ thị G. Một đường đi từ A đến B là một dãy các cạnh $(A_i, A_{i+1}) \ (i=\overline{0,k-1})$ với $A_0=A, A_k=B$. Số các cạnh (ở đây là $k$) tạo nên đường đi gọi là độ dài của đường đi.
Một đồ thị gọi là liên thông nếu giữa 2 đỉnh bất kì luôn có đường đi.
1.8. Định nghĩa 8 (Định nghĩa về tính liên thông)

Đường đi độ dài $n$ từ đỉnh $u$ đến đỉnh $v$, với $n$ là một số nguyên dương, trong đồ thị (giả đồ thị vô hướng hoặc đa đồ thị có hướng) $G=(V,E)$ là một dãy các cạnh (hoặc cung) $e_1, e_2, ..., e_n$ của đồ thị sao cho $e_1=(x_0,x_1),e_2=(x_1,x_2), ...,e_n=(x_{n-1},x_n)$, với $x_0=u$ và $x_n=v$. Khi đồ thị không có cạnh (hoặc cung) bội, ta ký hiệu đường đi này bằng dãy các đỉnh $x_0, x_1, ..., x_n$. Đường đi được gọi là chu trình nếu nó bắt đầu và kết thúc tại cùng một đỉnh.
Đường đi hoặc chu trình gọi là đơn nếu nó không chứa cùng một cạnh (hoặc cung) quá một lần.
Một đường đi hoặc chu trình không đi qua đỉnh nào quá một lần (trừ đỉnh đầu và đỉnh cuối của chu trình là trùng nhau) được gọi là đường đi hoặc chu trình sơ cấp. Rõ ràng rằng một đường đi (t.ư. chu trình) sơ cấp là đường đi (t.ư. chu trình) đơn.
1.9. Định nghĩa 9
Một đồ thị (vô hướng) được gọi là liên thông nếu có đường đi giữa mọi cặp đỉnh phân biệt của đồ thị.
Một đồ thị không liên thông là hợp của hai hay nhiều đồ thị con liên thông, mỗi cặp các đồ thị con này không có đỉnh chung. Các đồ thị con liên thông rời nhau như vậy được gọi là các thành phần liên thông của đồ thị đang xét. Như vậy, một đồ thị là liên thông khi và chỉ khi nó chỉ có một thành phần liên thông.
1.10. Định nghĩa 10 (Chu trình Hamilton)
Định nghĩa: Chu trình (t.ư. đường đi) sơ cấp chứa tất cả các đỉnh của đồ thị (vô hướng hoặc có hướng) G được gọi là chu trình (t.ư. đường đi) Hamilton. Một đồ thị có chứa một chu trình (t.ư. đường đi) Hamilton được gọi là đồ thị Hamilton (t.ư. nửa Hamilton).


II. CÁC ĐỊNH LÍ (VIỆC BỔ SUNG CÁC ĐỊNH LÍ BẮT ĐẦU . XIN MỜI CÁC BẠN)
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[TrauBo]

Định lý 1: (Định lý Mantel)

Cho G là một đồ thị (đơn, vô hướng) trên $n$ đỉnh. Nếu G không có tam giác thì G không có nhiều hơn $\left[ \dfrac{n^2}{4}\right]$ cạnh. Đẳng thức xảy ra khi và chỉ khi $G=K_{ \frac{n}{2} , \frac{n}{2}}$ nếu $n$ chẵn và $K_{\frac{n-1}{2} , \frac{n+1}{2}}$ nếu $n$ lẻ.
Chứng minh:

Goi I là một tập hợp các đỉnh độc lập (đôi một không có cạnh nối) cực đại và $| I | = x$. J là tập các đỉnh còn lại của G vậy $|J|=n-x$. Ta có các nhận xét sau:
$\bullet$ Mỗi cạnh của G có 1 đầu mút trong I, vì một cạnh nếu có cả 2 đầu mút sẽ khiến I không độc lập.
$\bullet \deg (A) \le x \ \forall A$. Thật vậy, vì G không có tam giác nên với mỗi đỉnh A, 2 đỉnh kề của A không kề nhau. Nói cách khác tập các đỉnh kề A là độc lập. Do ta giả sử $|I|$ là cực đại nên $\deg (A) \le x$.
Như vậy nếu $e$ là số cạnh của G thì $$e \le \sum_{A \in J} \deg (A) \le \sum_{A \in J} x = x(n-x) \le \left [ \dfrac{n^2}{4} \right ] $$

[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[batigoal]

Định lí 2 (Còn được gọi là bổ đề bắt tay.)
Cho đồ thị $G = (V, E)$. Khi đó
$$2|E| =\sum\limits_{v \in {\kern 1pt} V} {\deg (v)} $$

Chứng minh

Chứng minh
Mỗi cạnh $e = (u,v)$ được tính một lần trong $deg(u)$ và một lần trong $deg(v)$. Vậy tổng tất cả các bậc của các đỉnh bằng hai lần số cạnh.
Hệ quả: Số đỉnh bậc lẻ của một đồ thị là một số chẵn.

Áp dụng định lí này bạn đọc có thể giải quyết bài toán sau.

Không yêu cầu chứng minh bài toán ở topic này.

Trong một buổi họp có $n$ người tham gia và có một số cái bắt tay (mỗi cái bắt tay tạo thành từ hai người, hai người đã bắt rồi thì không bắt tay lại). Chứng minh rằng nếu số người tham gia bắt tay là một số lẻ thì số cái bắt tay được tạo ra là một số chẵn.

[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[TrauBo]

Định lý 3: Định lý Ramsey

Với mọi số nguyên dương $k, l$ tồn tại một số nguyên dương nhỏ nhất $R(k,l)$ thỏa mãn: Mọi cách tô màu các cạnh của một đồ thị đầy đủ trên $R(k,l)$ đỉnh bằng hai màu xanh và đỏ đều chứa một dồ thị con đầy đủ trên $k$ đỉnh màu xanh hoặc một đồ thị con đầy đủ trên $l$ đỉnh màu đỏ.
Chứng minh:

Ta chứng minh kết quả mạnh hơn: $R(k,l)$ hữu hạn và $$R(s,t) \le R(s-1,t) + R(s,t-1)\ \forall s,t \ge 2$$
Đặt $N=R(s-1,t)+R(s,t-1)$. Xét một cách tô màu xanh - đỏ các cạnh của một đồ thị $K_N$. Gọi A là một đỉnh bất kì. Trong $N-1$ cạnh kề A có không ít hơn $R(s-1,t)$ cạnh màu xanh hoặc $R(s,t-1)$ cạnh màu đỏ.
Giả sử có $R(s-1,t)$ cạnh màu xanh kề A. Các đầu mút khác A của các cạnh này tạo một đồ thị đầy đủ trên $R(s-1,t)$ đỉnh. Theo quy nạp, đồ thị này chứa hoặc một đồ thị con $K_{s-1}$ với các cạnh đỏ hoặc một đồ thị con $K_t$ với các cạnh xanh. Trong trường hợp đầu, lấy thêm đỉnh A ban đầu ta có đồ thị con $K_s$ đỉnh với các cạnh màu đỏ.

[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[hahahaha4]

Định lý 4: Định lý về đồ thị 2 phần.
Một đồ thị là 2 phần nếu và chỉ nếu không có chu trình sơ cấp độ dài lẻ

Đồ thị 2 phần là đồ thị mà ta có thể phân chia các đỉnh của nó thành hai tập hợp,mỗi tập hợp gồm các đỉnh độc lập với nhau.

Chứng minh:

+) Điều kiện cần: Nếu đồ thị là 2 phần.Một chu trình sẽ đi qua các đỉnh của của mỗi tập đỉnh độc lập 1 cách luân phiên nhau do đó chỉ qua lại đỉnh đầu tiên sau 1 số chẵn lần hay đồ thị có chu trình độ dài chẵn
+) Điều kiện đủ.Giả sử đồ thị $G$ không có chu trình đồ thị lẻ.Xét đỉnh có bậc lớn nhất trong $G$.Giả sử đó là đỉnh $A$.Chia tập đỉnh của $G$ thành 2 phần: phần $M$ chứa đỉnh $A$ và tất cả các đỉnh kề với $A$ và phần $N$ gồm các đỉnh còn lại.Đỉnh $A$ sẽ không được nối với các đỉnh thuộc tập $N$.Khi đó đưa đỉnh $A$ từ $M$ sang $N$.Xét trong tập $N$ đỉnh có bậc lớn nhất.Giả sử là $A_1$.(Dĩ nhiên bậc của nó nhỏ hơn $A$).Nếu $A_1$ nối với các đỉnh kề của $A$ thì các đỉnh kề của $A_1$ sẽ không được nối với bất kì đỉnh nào kề với $A$ nếu không ta sẽ có 1 chu trình độ dài lẻ.Khi đó ta thực hiện công đoạn chuyển các đỉnh kề của $A_1$ sang M.Còn nếu $A_1$ không được nối với bất kì đỉnh kề nào của $A$ ta chuyển $A_1$ sang $M$.Thực hiện liên tiếp quá trình này.Do số đỉnh là hữu hạn và số bậc giảm dần nên quá trình sẽ dừng lại.Ta được đồ thị hai phần

Chứng minh của mình.Mọi người cho ý kiến nhé.Rất thích cái topic này
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[TrauBo]

Định lý 5: (công thức Euler)
Cho G là một đồ thị phẳng liên thông với $n$ đỉnh, $e$ cạnh. Giả sử $f$ là số mặt của một biểu diễn phẳng của G thì $$n-e+f=2$$

Chứng minh:

Giả sử G liên thông. Để chứng minh công thức trên ta sẽ kiểm tra công thức cho các cây và chỉ ra rằng đại lượng $n-e+f$ không đổi khi ta thêm vào 1 cạnh.

Điều này được suy ra từ việc mọi đồ thị liên thông được xây dựng từ cây bằng cách mỗi lần cho thêm vào 1 cạnh, hơn nữa, nếu 1 đồ thị phẳng G nhận được từ đồ thị G' bằng cách thêm vào một cạnh thì G' cũng là đồ thị phẳng.

Ta kiểm tra cho cây, chú ý rằng với 1 cây, $n-e=1$. Hơn nữa, với 1 (biểu diễn phẳng của) cây, chỉ có duy nhất 1 mặt, đó chính là mặt không bị chặn. Thật vậy, mọi mặt bị chặn sẽ làm xuất hiện các chu trình trên đồ thị. Như vậy, với một cây ta có $f=1$ và công thức được kiểm chứng.

Giả sử công thức ta quan tâm đúng cho một đồ thị phẳng G' với $n'$ đỉnh, $e'$ cạnh và $f'$ mặt và sao cho ta có thể thêm 1 cạnh vào G' mà đồ thị mới G vẫn còn phẳng. Thế thì G có $n=n'$ đỉnh, $e=e'+1$ cạnh. Mặt khác cạnh mới thêm vào chia một mặt cũ (của G') thành 2 mặt mới (của G), các mặt khác không đổi. Thật vậy, giả thiết G là phẳng chứng tỏ cạnh mới thêm vào không cắt bất kì cạnh nào khác của G', do đó nằm hoàn toàn trong một trong các mặt của G '. Ngoài ra, tính liên thông của G' chứng tỏ không một đầu mút nào của cạnh thêm vào là cô lập. Như vậy G có $f=f'+1$ mặt. Công thức cho G' kéo theo công thức cho G.

Gõ mệt quá

[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[ptk_1411]

Bổ đề 3.1(tiếp theo về số Ramsey)

Với $R(m,n)$ là số Ramsey thì $$R(m,n)\le C_{m+n-2}^{n-1}$$

Chứng minh

Quy nạp theo $m+n$. Thế thì:
$$\begin{aligned} R(m,n)&\le R(m-1,n)+R(m,n-1)\\\\&\le C_{m+n-3}^{n-1}+C_{m+n-3}^{n-2}\\\\&=C_{m+n-2}^{n-1}\end{aligned}$$
Đẳng thức cuối theo công thức Pascal.$\square$

[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[hahahaha4]

Định lý 6 (Bất đẳng thức liên hệ giữa số cạnh đỉnh và số thành phần liên thông)
Một đồ thị có $n$ đỉnh,$k$ thành phần liên thông và $m$ cạnh thì ta có:
$$n-k \le m \le \dfrac{(n-k)(n-k+1)}{2}$$
Chứng minh:

$+)$Vế trái.
Ta quy nạp theo $n$.Với $n=1;2$ hiển nhiên.
Giả sử BDT đúng tới $n-1$ với $k$ thành phần liên thông và $m$ cạnh bất kì.ta chứng minh nó cũng đúng với $n$ đỉnh với $h$ thành phần liên thông và $f$ cạnh bât kì.Xét 1 đỉnh bất kì nằm ở 1 trong $h$ thành phần liên thông trên.Nếu đỉnh đó là đỉnh cô lập thì khi bỏ đỉnh đó đi thì ta có đồ thị với $n-1$ đỉnh.Áp dụng gt quy nạp ta có: $f \ge (n-1)-(h-1)=n-h$.Đúng.Nếu cạnh đó thuộc 1 thành phần liên thông nào đó và được nối với $a$ đỉnh trong thành phần liên thông đó.Khi đó ta bỏ đỉnh này đi thì ta có đồ thị với $(n-1)$ đỉnh $(f-a)$ cạnh và $h$ thành phần liên thông.Áp dụng gt quy nạp ta có: $(f-a) \ge (n-1)-h \Rightarrow f \ge n-h+a-1 \ge n-h$
Vậy ta có dpcm.
$+)$ BDT vế phải
Vẫn với Tư tưởng quy nạp ta có $n=1,2$ hiển nhiên
Giả sử đúng tới $n-1$ ta CM bất đẳng thức cũng đúng khi có $n$ đỉnh
Xét đồ thị với $f$ cạnh $n$ đỉnh và $h$ thành phần liên thông
Bỏ đi 1 đỉnh trong đồ thị.Nếu đỉnh đó cô lập.Theo gt quy nạp ta có:
$f \le \dfrac{[(n-1)-(h-1)][(n-1)-(h-1)+1]}{2}=\dfrac{(n-h)(n-h+1)}{2} (đúng$
Nếu đỉnh đó nằm trong 1 thành phần liên thông nào đó và được nối với $a$ đỉnh khác.Ta bỏ đinh đó và áp dụng gt quy nạp ta có:
$(f-a) \le \dfrac{[(n-1)-h][(n-1)-h+1}{2}$
$ \Rightarrow f \le a+\dfrac{(n-h-1)(n-h)}{2} \le n-h+\dfrac{(n-h)(n-h-1)}{2} \le \dfrac{(n-h)(n-h+1)}{2}$
Ta có dpcm

Cách khác chứng minh VP trong sách
Gọi $n_i$ là số đỉnh trong thành phần liên thông thứ $i$ khi đó ta có:
$\sum_{i=1}^{k}n_i=n \Rightarrow \sum_{i=1}^{k}(n_i-1)=n-k$
$ \Rightarrow \sum_{i=1}^{k}(n_i-1)^2 \le (n-k)^2 \Leftrightarrow \sum_{i=1}^{k}n_i^k \le (n-k)^2+2n-k$
Ta có: $m \le \sum_{i=1}^{k} C_{n_1}^{2}=\dfrac{1}{2}(\sum_{i=1}^{k}n_i^2-n) \le \dfrac{1}{2}[(n-k)^2+2n-k-n]=\dfrac{(n-k)(n-k+1)}{2}$

[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[batigoal]

Định lí 7.
Giữa mọi cặp đỉnh phân biệt của một đồ thị liên thông luôn có đường đi sơ cấp.

Đường đi sơ cấp bạn đọc xem ở mục định nghĩa 1.8 về tính liên thông của đồ thị

Chứng minh

Giả sử $u$ và $v$ là hai đỉnh phân biệt của một đồ thị liên thông $G$. Vì $G$ liên thông nên có ít nhất một đường đi giữa $u$ và $v$. Gọi $x_0, x_1, ..., x_n$, với $x_0=u$ và $x_n=v$, là dãy các đỉnh của đường đi có độ dài ngắn nhất. Đây chính là đường đi sơ cấp cần tìm. Thật vậy, giả sử nó không là đường đi đơn, khi đó $x_i=x_j$ với $0 \le i < j$. Điều này có nghĩa là giữa các đỉnh $u$ và $v$ có đường đi ngắn hơn qua các đỉnh $x_0, x_1, ..., x_{i-1}, x_j, ..., x_n$ nhận được bằng cách xoá đi các cạnh tương ứng với dãy các đỉnh $x_i, ..., x_{j-1}$.

[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[batigoal]

Định lí 8 (Định lý (Dirac, 1952) )
Nếu G là một đơn đồ thị có $n$ đỉnh và mọi đỉnh của $G$ đều có bậc không nhỏ hơn $\frac{n}{2}$ thì $G$ là một đồ thị Hamilton.
Chứng minh

Chứng minh: Định lý được chứng minh bằng phản chứng. Giả sử $G$ không có chu trình Hamilton. Ta thêm vào $G$ một số đỉnh mới và nối mỗi đỉnh mới này với mọi đỉnh của G, ta được đồ thị G’. Giả sử $k >0)$ là số tối thiểu các đỉnh cần thiết để $G’$ chứa một chu trình Hamilton. Như vậy, $G’$ có $n+k$ đỉnh.

Gọi $P$ là chu trình Hamilton $aeb ...a$ trong $G’$, trong đó $a$ và $b$ là các đỉnh của $G$, còn $y$ là một trong các đỉnh mới. Khi đó $b$ không kề với $a$, vì nếu trái lại thì ta có thể bỏ đỉnh $e$ và được chu trình $ab ...a$, mâu thuẩn với giả thiết về tính chất nhỏ nhất của $k$.
Ngoài ra, nếu $a’$ là một đỉnh kề nào đó của $a$ (khác với $e$) và $b’$ là đỉnh nối tiếp ngay $a’$ trong chu trình $P$ thì $b’$ không thể là đỉnh kề với $b$, vì nếu trái lại thì ta có thể thay $P$ bởi chu trình $aa’ ...bb’ ... a$, trong đó không có $e$, mâu thuẩn với giả thiết về tính chất nhỏ nhất của $k$.
Như vậy, với mỗi đỉnh kề với $a$, ta có một đỉnh không kề với $b$, tức là số đỉnh không kề với $b$ không thể ít hơn số đỉnh kề với $a$ (số đỉnh kề với $a$ không nhỏ hơn $\frac{n}{2} +k$). Mặt khác, theo giả thiết số đỉnh kề với $b$ cũng không nhỏ hơn $\frac{n}{2} +k$. Vì không có đỉnh nào vừa kề với b lại vừa không kề với b, nên số đỉnh của $G’$ không ít hơn $2(\frac{n}{2} +k)=n+2k$, mâu thuẫn với giả thiết là số đỉnh của G’ bằng $n+k (k>0)$. Định lý được chứng minh.

[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[nguyentram]

Định lí 9( Mở rộng của định lí dirac)
Nếu G là một đơn đồ thị có n đỉnh và tổng bậc của 2 đỉnh bất kì trong G không nhỏ hơn n thì G là một đồ thị Hamilton.
Chứng minh tương tự như định lí dirac
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[nghiepdu-socap]

Định lí 9( Mở rộng của định lí dirac)
Nếu G là một đơn đồ thị có n đỉnh và tổng bậc của 2 đỉnh bất kì trong G không nhỏ hơn n thì G là một đồ thị Hamilton.
Chứng minh tương tự như định lí dirac

Đây là định lý Ore, bạn bổ sung vào nhé
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]