Chứng minh: Bất đẳng thức n k m được chứng minh bằng quy nạp theo m. Nếu m=0 thì k=n nên bất đẳng thức đúng. Giả sử bất đẳng thức đúng đến m 1, với m 1. | CHƯƠNG III ĐỒ THỊ . Định lý Cho G là một đơn đồ thị có n đỉnh m cạnh và k thành phần liên thông. Khi đó n - k n - k 1 n - k m --- -------- . 2 Chứng minh Bất đẳng thức n - k m được chứng minh bằng quy nạp theo m. Nếu m 0 thì k n nên bất đẳng thức đúng. Giả sử bất đẳng thức đúng đến m-1 với m 1. Gọi G là đồ thị con bao trùm của G có số cạnh m0 là nhỏ nhất sao cho nó có k thành phần liên thông. Do đó việc loại bỏ bất cứ cạnh nào trong G cũng tăng số thành phần liên thông lên 1 và khi đó đồ thị thu được sẽ có n đỉnh k 1 thành phần liên thông và m0-1 cạnh. Theo giả thiết quy nạp ta có m0-1 n- k 1 hay m0 n-k. Vậy m n-k. Bổ sung cạnh vào G để nhận được đồ thị G có m1 cạnh sao cho k thành phần liên thông là những đồ thị đầy đủ. Ta có m m1 nên chỉ cần chứng minh m n - k n - k 1 37 Giả sử Gi và Gj là hai thành phần liên thông của G với ni và nj đỉnh và ni nj 1 . Nếu ta thay Gi và Gj bằng đồ thị đầy đủ với ni 1 và nj-1 đỉnh thì tổng số đỉnh không thay đổi nhưng số cạnh tăng thêm một lượng là ni 1 ni ni ni -1 2 2 nj nj -1 nj - 1 nj - 2 . _-------------- -------- n -nị 1. 2 2 i j Thủ tục này được lặp lại khi hai thành phần nào đó có số đỉnh thoả . Vì vậy m1 là lớn nhất n k là cố định khi đồ thị gồm k-1 đỉnh cô lập và một đồ thị đầy đủ với n-k 1 đỉnh. Từ đó suy ra bất đẳng thức cần tìm. . Định nghĩa Đồ thị có hướng G được gọi là liên thông mạnh nếu với hai đỉnh phân biệt bất kỳ u và v của G đều có đường đi từ u tới v và đường đi từ v tới u. Đồ thị có hướng G được gọi là liên thông yếu nếu đồ thị vô hướng nền của nó là liên thông. Đồ thị có hướng G được gọi là liên thông một chiều nếu với hai đỉnh phân biệt bất kỳ u và v của G đều có đường đi từ u tới v hoặc đường đi từ v tới u. Thí dụ 20 38 G G Đồ thị G là liên thông mạnh nhưng đồ thị G là liên thông yếu không có đường đi từ u tới x cũng như từ x tới u . . Mệnh đề Cho G là một đồ thị vô hướng hoặc có hướng với ma trận liền kề A theo thứ tự các đỉnh v1 v2 . vn. Khi đó số các đường đi khác nhau độ dài r từ vi tới
