Một đồ thị là một tập hợp gồm hữu hạn các điểm (gọi là đỉnh của đồ thị) cùng với tập hợp các đoạn đường cong hay thẳng (gọi là cạnh của đồ thị) có đầu mút tại các đỉnh của đồ thị.

Chú ý: Các cạnh của đồ thị thẳng hay cong, dài hay ngắn, các đỉnh ở vị trí nào đều không quan trọng.

Giả sử có đồ thị G:

- Tập hợp đỉnh V(G) = {A, B, C, D}. - Tập hợp cạnh E(G) = {AB, AC, AD, BC, CC}.

- Hai đỉnh kề nhau nếu chúng là hai đầu mút của một cạnh, ví dụ A – B.

- Một đỉnh không kề với đỉnh nào (kể cả chính nó) gọi là đỉnh cô lập.

- Cạnh có hai đầu mút trùng nhau gọi là khuyên, ví dụ CC.

Hai đỉnh A và B của một đồ thị gọi là liên thông nếu có một đường đi nối A với B.

Một đồ thị được gọi là liên thông nếu mọi cặp đỉnh của đồ thị (hai đỉnh bất kì) đều được nối với nhau bằng một đường đi.

Một cạnh CD của đồ thị gọi là một cầu nếu khi bỏ cạnh CD thì hai đỉnh C và D không còn liên thông nữa.

Mỗi đồ thị G không liên thông đều được chi thành một số đồ thị (gọi là đồ thị con của G) liên thông, rời nhau; mỗi đồ thị con đó gọi là một thành phần liên thông của đồ thị G.

Một đồ thị 2n đỉnh, mỗi đỉnh bậc ít nhất bằng n, là đồ thị liên thông.

1) Cho hai đồ thị như hình dưới:

Trong đồ thị ở Hình a), 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. Trong đồ thị ở Hình b), mỗi đỉnh thuộc khối đỉnh bên trái đều không thể nối được với mỗi đỉnh thuộc khối đỉnh bên phải bằng một đường đi. Vậy đồ thị đó là đồ thị không liền thông.

2) Giả sử một lớp có 40 học sinh. Biết rằng mỗi em có số điện thoại của ít nhất là 20 bạn trong lớp và nếu bạn A có số điện thoại của bạn B thì bạn B cũng có số điện thoại của bạn A. Chứng minh rằng bất cứ hai em nào trong lớp cũng có số điện thoại của nhau.

Giải:

Ta đặt tương ứng mỗi em học sinh trong lớp với một đỉnh của đồ thị và hai đỉnh được gọi là liên thông nếu hai em có số điện thoại của nhau. Bài toán trở thành: Cho một đồ thị có 40 đỉnh. Biết mỗi đỉnh bất kì đều liên thông với ít nhất 20 đỉnh khác. Chứng minh rằng đồ thị là liên thông. Đồ thị này có 40 đỉnh, mỗi đỉnh có bậc ít nhất là 20, do đó đồ thị là liên thông. Vậy, bất cứ hai em học sinh nào trong lớp cũng có số điện thoại của nhau.