Ramsey numbers

Các bạn đọc lại các bài sau để theo dõi cho dễ:

—

Trong khi chuẩn bị cho các kỳ thi chọn học sinh giỏi, các bạn học sinh có lẽ đã gặp ví dụ sau nhiều lần.

Ví dụ 1. Trong mỗi nhóm sáu người luôn có ba người đôi một quen nhau hoặc đôi một không quen nhau.

Lời giải. Gọi $A$ là một người trong nhóm sáu người ta đang quan tâm. Vì với mỗi một trong năm người còn lại, $A$ sẽ quen hoặc không quen người đó, suy ra trong năm người còn lại ta tìm được ba người, gọi là $B$ , $C$ , $D$ , mà $A$ cùng quen hoặc cùng không quen họ. Giả sử mà không làm mất tính tổng quát rằng $A$ quen cả ba người $B$ , $C$ , và $D$ . Nếu trong $B$ , $C$ , và $D$ có hai người quen nhau, chẳng hạn là $B$ và $C$ thì ba người $A$ , $B$ , và $C$ đôi một quen nhau. Nếu không, $B$ , $C$ , và $D$ đôi một không quen nhau. $\Box$

Chứng minh là ví dụ đầu tiên của lý thuyết Ramsey. Không khó khăn lắm ta thấy với một nhóm ít hơn sáu người thì kết luận không còn đúng.

Bây giờ cho mỗi người ứng với một đỉnh của đồ thị đầy đủ $K_6$ trên sáu đỉnh. Hai người được nối với nhau bởi một cạnh đỏ nếu họ quen nhau, được nối với nhau bởi một cạnh xanh nếu họ không quen nhau. Theo ví dụ trên thì với mọi cách tô các cạnh của $K_6$ bởi hai màu, luôn có $K_3$ mà các cạnh của nó mang cùng một màu. Hơn nữa, kết luận không còn đúng nếu thay $K_6$ bởi $K_n$ với $n<6$ . Kết quả sẽ thay đổi thế nào nếu thay $K_3$ bởi $K_{\alpha}$ ? Ta xét bài toán tổng quát sau:

Bài toán. Cho một số nguyên dương $\alpha$ . Tồn tại hay không số nguyên dương $n$ có tính chất: Với mỗi cách tô màu các cạnh của $K_n$ bởi hai màu, luôn có $K_{\alpha}$ mà các cạnh mang cùng một màu. Số nguyên dương $n$ nhỏ nhất có tính chất này bằng bao nhiêu?

Với câu hỏi đầu tiên thì định lý tổng quát sau cho câu trả lời là tồn tại. Câu hỏi thứ hai rất khó, hiện tại ta không thể tính được $n$ như một hàm của $\alpha$ trong tình huống tổng quát mà chỉ có thể ước lượng nó.

Định lý 1 (Ramsey). Cho $s$ và $t$ là hai số nguyên lớn hơn $1$ . Khi đó tồn tại số nguyên dương $n$ có tính chất: Với mỗi cách tô màu các cạnh của $K_n$ bởi hai màu xanh và đỏ, $K_n$ có đồ thị con $K_s$ với các cạnh xanh hoặc có đồ thị con $K_t$ với các cạnh đỏ. Nếu ký hiệu $R(s,t)$ là số nguyên dương $n$ nhỏ nhất có tính chất này thì

$R(s,t)\leq R(s,t-1)+R(s-1,t)$

mỗi khi $s$ và $t$ lớn hơn $2$ .

Các số $R(s,t)$ được gọi là các số Ramsey. Phần thảo luận lúc đầu cho ta biết $R(3,3)=6$ . Từ bất đẳng thức trên ta có thể tìm được một cận trên của các số Ramsey. Mục đính chính của bài là dùng phương pháp xác suất đưa ra một cận dưới của các số $R(k,k)$ , chúng được gọi là các số Ramsey đối xứng.

Chứng minh. Ta chứng minh bằng quy nạp theo $s$ và $t$ . Lập luận đơn giản ta thu được $R(k,2)$ , $R(2,k)$ đều tồn tại và bằng $k$ với mọi $k>1$ .

Bây giờ giả sử $R(s,t-1)$ và $R(s-1,t)$ đều tồn tại, ở đây $s$ và $t$ là các số nguyên lớn hơn $2$ . Đặt $\alpha=R(s,t-1)+R(s-1,t)$ . Xét một cách tô màu các cạnh của $K_{\alpha}$ bởi một trong hai màu xanh và đỏ. Gọi $v$ là một đỉnh của $K_{\alpha}$ . Mỗi một trong $\alpha-1$ đỉnh còn lại của $K_{\alpha}$ được nối với $v$ bởi một cạnh xanh hoặc đỏ. Suy ra, trong các đỉnh này có $R(s-1,t)$ đỉnh được nối với $v$ bởi cạnh xanh, hoặc có $R(s,t-1)$ đỉnh được nối với $v$ bởi cạnh đỏ. Ta xét tình huống thứ nhất, tình huống còn lại được lập luận hoàn toàn tương tự. Xem $R(s-1,t)$ đỉnh như một đồ thị đầy đủ. Theo giả thiết quy nạp, trong đồ thị đầy đủ này có $K_{s-1}$ với các cạnh xanh hoặc $K_t$ với các cạnh đỏ. Nếu có $K_t$ với các cạnh đỏ thì ta có điều phải chứng minh, nếu có $K_{s-1}$ với các cạnh xanh thì thêm $v$ vào ta có đồ thị con $K_s$ của $K_{\alpha}$ với các cạnh xanh, và ta cũng có điều cần chứng minh. $\Box$

Định lý 2. Với mỗi số nguyên $k>3$ , ta có $R(k,k)>2^{k/2}$ .

Chứng minh (của Paul Erdos). Xét một số nguyên $n$ thỏa mãn $k\leq n\leq 2^{k/2}$ . Định lý sẽ được chứng minh nếu ta chỉ ra rằng tồn tại một cách tô màu các cạnh của $K_n$ bởi hai màu xanh và đỏ, sao cho trong $K_n$ không có $K_k$ với các cạnh cùng màu.

Tô màu mỗi cạnh của $K_n$ bởi một trong hai màu xanh và đỏ một cách ngẫu nhiên. Như vậy ta có một không gian xác suất rời rạc với không gian mẫu $\Omega$ là tập tất cả các cách tô màu, và với mỗi biến cố $A$ , xác suất xảy ra $A$ bằng $\mid A\mid /\mid\Omega\mid$ .

Gọi $X$ là biến cố: trong $K_n$ không có $K_k$ với các cạnh cùng màu. Ta cần chứng $\mathbb{P}(X)>0$ . Với mỗi đồ thị con đầy đủ trên $k$ đỉnh của $K_n$ , gọi $Y_{\alpha}$ là biến cố: $\alpha$ có các cạnh cùng màu. Khi đó

$\displaystyle\mathbb{P}(Y_{\alpha})=\frac{\mid Y_{\alpha}\mid }{\mid \Omega\mid}=\frac{2\cdot 2^{C_n^2-C_k^2}}{2^{C_n^2}}=2^{1-C_k^2},$

do đó

$\mathbb{P}(X)=1-\mathbb{P}(\overline{X}) =1-\mathbb{P}\left(\bigcup_{\alpha}Y_{\alpha}\right)\geq 1-\sum_{\alpha}\mathbb{P}(Y_{\alpha})=1-C_n^k2^{1-C_k^2}.$

Mà ta lại có

$\displaystyle C_n^k2^{1-C_k^2}<\frac{n^k}{k!}\cdot 2^{1-C_k^2}\leq \frac{2^{k^2/2}}{k!}\cdot 2^{1-C_k^2}=\frac{2^{1+\frac{k}{2}}}{k!}< 1,$

suy ra $\mathbb{P}(X)>0$ . $\Box$

Bipartite graph

Một đồ thị $G$ được gọi là hai phần (hay lưỡng phân) nếu $V(G)$ có thể phân hoạch thành hai tập con $X$ và $Y$ , sao cho mỗi phần tử của $E(G)$ có một đầu mút trong $X$ và đầu mút còn lại trong $Y$ . Khi đó $X$ và $Y$ được gọi là các phần của đồ thị lưỡng phân. Ta ký hiệu đồ thị lưỡng phân với hai phần $X$ và $Y$ bởi $G[X,Y]$ . Nếu trong $G[X,Y]$ , mọi đỉnh thuộc $X$ được nối với mọi đỉnh của $Y$ thì $G[X,Y]$ được gọi là đồ thị lưỡng phân đầy đủ.

Ví dụ 1. Gọi $X$ và $Y$ lần lượt là tập các cầu thủ bóng đá và tập các câu lạc bộ trong một thành phố. Khi đó ta có đồ thị lưỡng phân $G[X,Y]$ , ở đây $x\in X$ được nối với $y\in Y$ khi và chỉ khi $x$ đã từng chơi cho $y$ .

Ví dụ 2 (Bài toán tối ưu trong đường sắt). Giả sử ta có một lịch trình các chuyến tàu cùng các điểm dừng của chúng, và cần tìm một tập hợp các ga tàu càng nhỏ càng tốt sao cho mọi chuyến tàu ghé thăm ít nhất một trong các ga đã chọn. Bài toán này có thể được mô hình hóa như một bài toán trên đồ thị lưỡng phân có các phần là tập các chuyến tàu và tập các ga tàu, mỗi chuyến tàu nối với ga mà nó sẽ dừng.

Bây giờ chúng tôi sẽ giới thiệu một số kết quả cơ bản về đồ thị hai phần.

Định lý 1. Cho đồ thị lưỡng phân $G[X,Y]$ không có đỉnh cô lập và thỏa mãn $\deg (x)\geq \deg (y)$ với mọi $xy\in E(G)$ ( $x\in X$ và $y\in Y$ ). Khi đó $\mid X\mid \leq \mid Y\mid$ . Đẳng thức xảy ra khi và chỉ khi $\deg (x)= \deg (y)$ với mọi $xy\in E(G)$ ( $x\in X$ và $y\in Y$ ).

Chứng minh. Vì $G$ không có đỉnh cô lập nên với mỗi $(x,y)\in X\times Y$ , ta có

$\displaystyle \sum_{y^{\prime}\in N(x)}\frac{1}{\deg (x)}=\sum_{x^{\prime}\in N(y)}\frac{1}{\deg (y)}=1.$

Suy ra

$\displaystyle \mid X\mid =\sum_{x\in X}\sum_{y\in N(x)}\frac{1}{\deg (x)}=\sum_{\substack{(x,y)\in X\times Y\\ xy\in E(G)}}\frac{1}{\deg x},$

và

$\displaystyle \mid Y\mid =\sum_{y\in Y}\sum_{x\in N(y)}\frac{1}{\deg (y)}=\sum_{\substack{(x,y)\in X\times Y\\ xy\in E(G)}}\frac{1}{\deg y}.$

Kết hợp với giả thiết $\deg (x)\geq \deg (y)$ với mọi $xy\in E(G)$ ( $x\in X$ và $y\in Y$ ) ta có những điều cần chứng minh. $\Box$

Định lý 2. Một đồ thị là lưỡng phân khi và chỉ khi nó không chứa chu trình độ dài lẻ.

Chứng minh. Nếu một đồ thị là lưỡng phân thì dọc theo một chu trình của nó, các đỉnh thuộc hai phần sẽ xuất hiện luân phiên. Vì thế, mỗi chu trình trong đồ thị lưỡng phân phải có độ dài là số chẵn. Bây giờ xét một đồ thị $G$ không chứa chu trình với độ dài là số lẻ. Ta chỉ cần xét tình huống $G$ là một đồ thị liên thông.

Gọi $T$ là một cây bao trùm trong $G$ (nó tồn tại theo [1]), và chọn một đỉnh $r$ làm gốc của cây này. Gọi $C$ là tập tất cả các đỉnh mà đường đi trong $T$ nối $r$ với nó có độ dài chẵn, và $L$ là tập tất cả các đỉnh mà đường đi trong $T$ nối $r$ với nó có độ dài chẵn. Khi đó $V(G)$ được phân hoạch thành hai phần $C$ và $L$ .

Ta sẽ chứng minh $G$ là đồ thị lưỡng phân với các phần là $L$ và $C$ . Xét hai đỉnh kề nhau $x$ và $y$ của $G$ . Nếu $xy\in T$ thì độ dài của $rTx$ và độ dài của $rTy$ khác tính chẵn-lẻ, do đó trong hai đỉnh $x$ , $y$ có một đỉnh thuộc $C$ và đỉnh còn lại thuộc $L$ . Nếu $xy\not \in T$ , từ giả thiết ta thấy chu trình $xTy\cup xy$ có độ dài chẵn. Theo phần chứng minh trước thì mỗi cạnh khác $xy$ thuộc chu trình này có các đầu mút thuộc hai phần khác nhau của phân hoạch, suy ra $x$ và $y$ thuộc hai phần khác nhau của phân hoạch. $\Box$

Tài liệu tham khảo

[1] https://nttuan.org/2024/08/02/tree/

Tree

Một đồ thị không chứa chu trình được gọi là một rừng. Một rừng liên thông được gọi là một cây.

Ví dụ 1. Cho $G$ là một cây trên $n>1$ đỉnh. Chứng minh rằng $G$ có ít nhất hai lá, và nếu $v$ là một lá thì $G\setminus\{v\}$ là một cây.

Hướng dẫn. Trong các đường đi của $G$ , quan tâm đến một đường đi dài nhất. Chứng minh hai đầu của nó là lá. Chỉ ra $G\setminus\{v\}$ là một rừng liên thông. $\Box$

Định lý 1. Với một đồ thị $G$ , các khẳng định sau là tương đương:

(1) $G$ là một cây;

(2) Mỗi hai đỉnh của $G$ được nối với nhau bởi một đường đi duy nhất trong $G$ ;

(3) $G$ là đồ thị liên thông và với mỗi cạnh $e$ , đồ thị có được từ $G$ bằng cách bỏ đi cạnh $e$ không phải là đồ thị liên thông;

(4) $G$ không chứa chu trình và với mỗi hai đỉnh không kề nhau $x$ và $y$ , đồ thị có được từ $G$ bằng cách thêm vào cạnh $xy$ chứa một chu trình.

Chứng minh. Giả sử $G$ là một cây và $x$ , $y$ là hai đỉnh của $G$ . Vì $G$ là đồ thị liên thông nên có một đường đi nối $x$ và $y$ , ký hiệu là $\alpha$ . Nếu có một đường đi khác đường đi này nối $x$ và $y$ , ký hiệu là $\beta$ , gọi $z$ là đỉnh chung gần $x$ nhất của hai đường đi. Đường đi từ $x$ đến $z$ dọc theo $\alpha$ hợp với đường đi từ $z$ đến $x$ dọc theo $\beta$ tạo thành một chu trình, vô lý. Vậy ta đã chứng minh $(1)\Rightarrow (2)$ .

Xét một cạnh $e=xy$ của $G$ . Nếu đồ thị có được từ $G$ bằng cách bỏ đi cạnh $e$ là đồ thị liên thông, thì trong $G$ có một đường đi nối $x$ và $y$ mà không chứa $e$ . Đường đi này cùng với $e$ là hai đường đi nối $x$ và $y$ . Vậy ta đã chứng minh $(2)\Rightarrow (3)$ , vì nếu có $(2)$ thì đồ thị phải là đồ thị liên thông.

Bây giờ giả sử có $(3)$ . Trước tiên ta thấy $G$ không chứa chu trình, vì nếu không ta bỏ đi một cạnh của chu trình thì đồ thị mới vẫn liên thông, vô lý. Xét hai đỉnh không kề nhau $x$ và $y$ . Vì $G$ là đồ thị liên thông nên có đường đi nối $x$ và $y$ . Thêm cạnh $xy$ vào đường đi này ta có một chu trình trong đồ thị có được từ $G$ bằng cách thêm vào cạnh $xy$ . Vậy ta có $(4)$ .

Cuối cùng, ta giả sử có $(4)$ . Xét hai đỉnh phân biệt $x$ và $y$ . Nếu $x$ và $y$ kề nhau thì có đường đi nối $x$ và $y$ , là $xy$ chẳng hạn. Nếu $x$ và $y$ không kề nhau thì đồ thị có được từ $G$ bằng cách thêm vào cạnh $xy$ chứa một chu trình. Vì $G$ không chứa chu trình nên chu trình này chứa $xy$ , bỏ $xy$ ra khỏi nó ta có đường đi trong $G$ nối $x$ và $y$ . Vậy ta có $(1)$ . $\Box$

Hệ quả. Một đồ thị liên thông trên $n$ đỉnh là một cây khi và chỉ khi nó có $n-1$ cạnh.

Chứng minh. Giả sử $G$ là một cây trên $n$ đỉnh. Vì $G$ là đồ thị liên thông nên theo định lý 1 trong [4], ta có thể đánh số các đỉnh của $G$ là $v_1$ , $v_2$ , $\ldots$ , $v_n$ sao cho $G_i:=G[v_1,v_2,\ldots,v_i]$ là đồ thị liên thông với mọi $i$ . Do $G$ là một cây nên mỗi $G_i$ là một cây. Giả sử $G_i$ có $i-1$ cạnh với mọi chỉ số $i<k$ ( $k$ là một số nguyên dương sao cho $k\leq n$ ). Vì $G_k$ là liên thông nên với mỗi $i<k$ , có đường đi trong $G_k$ nối $v_i$ và $v_k$ . Trong tất cả các đường đi như thế, xét đường đi ngắn nhất và giả sử nó nối $v_1$ và $v_k$ . Đường đi này phải có độ dài bằng $1$ , hay $v_k$ và $v_1$ kề nhau trong $G$ . Vì $G$ không có chu trình nên trong $G_{k-1}$ , chỉ có đúng một đỉnh kề với $v_k$ , suy ra $G_k$ có $k-2+1=k-1$ cạnh. Theo nguyên lý quy nạp toán học, $G=G_n$ có $n-1$ cạnh.

Ngược lại, giả sử $G$ là một đồ thị liên thông trên $n$ đỉnh và có $n-1$ cạnh. Gọi $T$ là một đồ thị con bao trùm liên thông cực tiểu của $G$ . Do tính cực tiểu, khi bỏ mỗi cạnh ra khỏi $T$ thì đồ thị thu được không liên thông, suy ra theo định lý 1 thì $T$ là một cây. Cây này có số cạnh bằng $n-1$ theo phần đầu của chứng minh, do đó $T=G$ . $\Box$

Trong một số vấn đề, việc xét một cây với gốc sẽ rất thuận tiện. Giả sử có một cây $T$ và một đỉnh cố định $r$ , gọi là gốc của cây. Với hai đỉnh $x$ và $y$ của $T$ , có đúng một đường đi nối $x$ và $y$ , ta ký hiệu nó là $xTy$ . Với $a,b\in T$ , ta viết $a\leq_T b$ (hoặc $a\leq b$ khi không sợ nhầm lẫn) nếu $a\in rTb$ . Ta thấy $\leq_T$ là một quan hệ thứ tự bộ phận trên $T$ , gọi là thứ tự cây. Khi $a<b$ ta nói $b$ nằm trên $a$ , hay $a$ nằm dưới $b$ . Theo quan hệ thứ tự này thì $r$ là phần tử nhỏ nhất của $T$ , mỗi lá là phần tử cực đại. Hai đầu mút của mỗi cạnh của $T$ là so sánh được.

Ví dụ 2. Cho số nguyên $n$ lớn hơn $1$ và một cây trên $n$ đỉnh. Các đỉnh của cây được viết các số thực $x_1$ , $x_2$ , $\ldots$ , $x_n$ . Mỗi cạnh của cây được viết tích của hai số được viết trên các đầu mút của cạnh, gọi $S$ là tổng tất cả các số này. Chứng minh rằng

$\displaystyle\sqrt{n-1}\left(x_1^2+x_2^2+\dots+x_n^2\right)\geq 2S.$

Lời giải. Giả sử tập các đỉnh của cây là $V=\{v_1, v_2, \ldots, v_n\}$ sao cho với mỗi $i$ , số được viết trên $v_i$ là $x_i$ . Với hai đỉnh kề nhau $v_i$ và $v_j$ , gọi $P(i,j)$ là tập các đỉnh của cây không nối được đến $v_i$ bởi một đường đi sau khi xóa khỏi cây cạnh $v_iv_j$ . Ta có ngay $1\leq \mid P(i,j)\mid \leq n-1$ mỗi khi $v_i$ và $v_j$ kề nhau.

Nhận xét 1. Nếu $v_i$ và $v_j$ kề nhau thì $\mid P(i,j)\mid +\mid P(j,i)\mid=n$ .

Chứng minh. Gọi $v$ là một đỉnh của cây, và xem nó là gốc. Ta có $v_i$ và $v_j$ là so sánh được theo thứ tự cây. Nếu $v_i<v_j$ thì $v\in P(j,i)$ , nếu $v_j<v_i$ thì $v\in P(i,j)$ , nhưng không thể có cả hai. Như vậy $V$ được phân hoạch thành $P(i,j)$ và $P(j,i)$ , từ đây ta có điều cần chứng minh. $\Box$

Nhận xét 2. Với mỗi $i$ ,

$\displaystyle \sum_{v_j\in N(v_i)}\mid P(i,j)\mid =n-1$ .

Chứng minh. Cố định một chỉ số $i$ . Do mỗi đỉnh đều nối đến $v_i$ bởi một đường đi duy nhất và cây không có chu trình nên các $P(i,j)$ với $v_j\in N(v_i)$ làm thành một phân hoạch của $V\setminus\{v_i\}$ , từ đây ta có điều cần chứng minh. $\Box$

Bây giờ với mỗi cạnh $v_iv_j$ , theo nhận xét 1 ta có

$\displaystyle \mid P(i,j)\mid .\mid P(j,i)\mid=\frac{n^2-(\mid P(i,j)\mid -\mid P(j,i)\mid)^2}{4}\geq n-1,$

suy ra

$\displaystyle\frac{\mid P(i,j)\mid}{\sqrt{n-1}}x_i^2+\frac{\mid P(j,i)\mid}{\sqrt{n-1}}x_j^2\geq 2\sqrt{\frac{\mid P(i,j)\mid .\mid P(j,i)\mid}{n-1}}|x_ix_j|\geq 2x_ix_j.$

Mỗi cạnh cho ta một bất đẳng thức có dạng như trên, cộng theo vế các bất đẳng thức này ta có bất đẳng thức trong đề bài. $\Box$

Tài liệu tham khảo

[1] https://nttuan.org/2009/08/13/graph01/

[2] https://nttuan.org/2023/09/01/graph02/

[3] https://nttuan.org/2024/06/04/graph03/

[4] https://nttuan.org/2024/07/01/connected-graph/

Connected graph

Một đồ thị (xem lại [2]) khác rỗng $G$ được gọi là liên thông nếu mỗi hai đỉnh của nó được nối với nhau bởi một đường đi (xem lại [3]).

Định lý 1. Các đỉnh của một đồ thị liên thông $G$ có thể đánh số $v_1$ , $v_2$ , $\ldots$ , $v_n$ sao cho $G_i:=G[v_1,v_2,\ldots,v_i]$ là đồ thị liên thông với mọi $i$ .

Chứng minh. Lấy một đỉnh $v_1$ , và giả sử đã đánh số được các đỉnh $v_1$ , $v_2$ , $\ldots$ , $v_i$ thỏa mãn tính chất trong định lý, ở đây $i<\mid G\mid.$ Giả sử $v$ là một đỉnh khác tất cả các đỉnh đã được đánh số. Vì $G$ là đồ thị liên thông nên tồn tại đường đi $P$ nối $v$ với $v_1$ . Chọn $v_{i+1}$ là đỉnh cuối của $P$ mà không thuộc $G_i$ , khi đó $v_{i+1}$ có một láng giềng trong $G_i$ và $G_{i+1}$ liên thông. $\Box$

Hệ quả. Một đồ thị liên thông trên $n$ đỉnh sẽ có ít nhất $n-1$ cạnh.

Chứng minh. Quy nạp theo $n$ và dùng định lý 1. Bạn đọc tự chứng minh xem như một bài tập. $\Box$

Cho đồ thị $G=G(V,E)$ . Một đồ thị con liên thông cực đại (cực đại theo nghĩa không có đồ thị con liên thông chứa và khác nó, xem lại [2]) của $G$ được gọi là thành phần liên thông của $G$ . Đương nhiên, các thành phần liên thông là các đồ thị con cảm sinh (xem lại [2]) của $G$ , và tập các đỉnh của chúng lập thành một phân hoạch của $V$ . Một đồ thị là liên thông nếu và chỉ nếu nó có đúng một thành phần liên thông.

Ví dụ 1. Cho $G$ là một đồ thị với $m$ cạnh và $p$ thành phần liên thông. Chứng minh rằng $m+p\geq \mid G\mid$ .

Lời giải. Gọi $n_i$ là số đỉnh của thành phần liên thông thứ $i$ . Khi đó số cạnh của thành phần liên thông thứ $i$ không bé hơn $n_i-1$ , do đó

$m\geq \sum (n_i-1)=-p+\sum n_i=\mid G\mid -p,$

và bài toán được giải. $\Box$

Ví dụ 2. Cho $G$ là một đồ thị con không liên thông của $K_n$ . Chứng minh rằng $\overline{G}$ là một đồ thị con liên thông của $K_n$ .

Lời giải. Gọi $G^{\prime}$ là một thành phần liên thông của $G$ . Vì $G$ không liên thông nên $G\setminus G^{\prime}$ khác rỗng. Do tính cực đại của thành phần liên thông, không có cạnh nào của $G$ nối một đỉnh của $G^{\prime}$ với một đỉnh của $G\setminus G^{\prime}$ . Suy ra trong $\overline{G}$ , mỗi đỉnh của $G^{\prime}$ sẽ nối với mỗi đỉnh của $G\setminus G^{\prime}$ .

Vậy muốn chứng minh $\overline{G}$ liên thông, ta chỉ cần chứng minh hai đỉnh cùng thuộc $G^{\prime}$ hoặc $G\setminus G^{\prime}$ được nối với nhau. Nếu hai đỉnh cùng thuộc $G^{\prime}$ thì ta nối chúng với nhau qua một đỉnh của $G\setminus G^{\prime}$ , và ngược lại. $\Box$

Cho số tự nhiên $k$ . Một đồ thị $G=(V,E)$ được gọi là $k-$liên thông nếu $k<\mid G\mid$ và $G\setminus X$ vẫn là đồ thị liên thông với mọi $X\subset V$ mà $\mid X\mid<k$ . Số $k$ lớn nhất sao cho $G$ là $k-$ liên thông được gọi là chỉ số liên thông của $G$ , ký hiệu $k(G)$ .

Ví dụ 3. $k(K_n)=n-1$ với mỗi số nguyên dương $n$ .

Lời giải. Bạn đọc tự giải xem như bài tập. $\Box$

Định lý 2 (Whitney, 1932). Cho đồ thị $G=(V,E)$ với $\mid G\mid\geq 3$ . Khi đó $G$ là $2-$ liên thông khi và chỉ khi với hai đỉnh phân biệt bất kỳ của $G$ , tồn tại hai đường đi rời nhau nối chúng (hai đường đi được gọi là rời nhau nếu chúng không có đỉnh trong chung).

Chứng minh. Khẳng định đúng hiển nhiên khi $\mid G\mid =3$ . Bây giờ ta xét $\mid G\mid >3$ . Đầu tiên, giả sử với hai đỉnh phân biệt bất kỳ của $G$ tồn tại hai đường đi rời nhau nối chúng. Gọi $w$ là một đỉnh bất kỳ và $u,v$ là hai đỉnh khác nhau của $G\setminus\{w\}$ . Giữa $u$ và $v$ sẽ có hai đường đi rời nhau nối chúng, $w$ sẽ không thuộc một trong hai đường này, ký hiệu $P$ . Ta có $P$ là một đường trong $G\setminus\{w\}$ nối $u$ và $v$ . Suy ra $G\setminus\{w\}$ liên thông, do đó $G$ là $2-$ liên thông.

Bây giờ giả sử $G$ là $2-$ liên thông và tồn tại hai đỉnh phân biệt $u$ và $v$ mà không có hai đường đi rời nhau. Vì $\mid G\mid >3$ nên tồn tại ít nhất hai đường đi nối $u$ và $v$ . Gọi $P$ và $Q$ là hai đường đi nối $u$ và $v$ mà có tập đỉnh chung $S$ có ít phần tử nhất có thể. Lấy $w\in S\setminus \{u,v\}$ và $P_1$ , $P_2$ là phần của $P$ từ $u$ đến $w$ , $w$ đến $v$ . Tương tự ta định nghĩa $Q_1$ và $Q_2$ .

Vì $G$ là $2-$ liên thông, ta có thể lấy một đường đi $R$ ngắn nhất từ một đỉnh $x$ thuộc $(P_1\cup Q_1)\setminus \{w\}$ đến một đỉnh $y$ thuộc $(P_2\cup Q_2)\setminus \{w\}$ mà không qua $w$ . Giả sử mà không làm mất tính tổng quát rằng $x\in P_1$ và $y\in Q_2$ . Gọi $T$ là đường đi nối $u$ với $v$ được hình thành bởi phần $P_1$ nối $u$ với $x$ , và phần $Q_2$ nối $y$ với $v$ , cùng với $R$ . Do cách chọn $R$ , hai đường đi $T$ và $Q_1\cup P_2$ cùng nối $u$ với $v$ nhưng có tập các đỉnh chung là tập con của $S\setminus \{w\}$ , vô lý. $\Box$

Cho một đồ thị $G$ . Đường đi $P$ (không nhất thiết trong $G$ ) được gọi là $G-$ đường nếu $\mid P\mid >1$ và $P\cap G$ chỉ chứa hai đầu mút của $P$ . Kết quả sau cho ta biết cấu trúc của các đồ thị $2-$ liên thông.

Định lý 3. Một đồ thị là $2-$ liên thông khi và chỉ khi nó có thể được dựng từ một chu trình bằng cách bổ sung liên tiếp các $H-$ đường vào các đồ thị $H$ đã được dựng.