Có bao nhiêu đỉnh bậc lẻ trong đồ thị ở Hình 5a?

+) Ví dụ về đồ thị liên thông:

Ở hình trên, hai đỉnh bất kì của đồ thị đều được nối với nhau bằng một đường đi. Vậy đồ thị đó là đồ thị liên thông.

+) Ví dụ về đồ thị không liên thông:

Ở hình trên, mỗi đỉnh thuộc khối bên trên đều không thể nối được với mỗi đỉnh thuộc khối bên dưới bằng một đường đi. Vậy đồ thị đó là đồ thị không liên thông.

Gọi 6 người bất kì là A, B, C, D, E, G.

Trong 6 người đó ta chọn ra một người A.Trong 5 người còn lại ta chia thành 2 nhóm:

- Nhóm 1 gồm những người quen A.

- Nhóm 2 gồm những người không quen A.

Có 5 người mà chỉ có 2 nhóm. Do đó, tồn tại ít nhất 3 người thuộc cùng một nhóm. Tức là tồn tại ít nhất 3 người quen A hoặc tồn tại ít nhất 3 người không quen A.

- Nếu tồn tại ít nhất 3 người quen A. Gọi 3 người đó là B, C, D:

+ Nếu trong 3 người B, C, D có 2 người nào đó quen nhau. Giả sử 2 người đó là B và C thì ta có 3 người A, B, C là 3 người đôi một quen nhau.

+ Nếu trong 3 người B, C, D không có 2 người nào đó quen nhau thì 3 người B, C, D là 3 người đôi một không quen nhau.

- Nếu tồn tại 3 người không quen A. Giả sử 3 người đó là D, E, G:

+ Trong 3 người D, E, G nếu có 2 người nào đó không quen nhau. Giả sử 2 người đó là D và E thì 3 người A, D, E là 3 người đôi một không quen nhau.

+ Nếu trong 3 người D, E, G không có 2 người nào không quen nhau thì 3 người D, E, G là 3 người đôi một quen nhau.

Vậy trong 6 người bất kì luôn tồn tại 3 người đôi một quen nhau hoặc 3 người đôi một không quen nhau (đpcm).