Đị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]