Định lý Kuratowski

Trong lý thuyết đồ thị, định lý Kuratowski, được phát triển bởi nhà toán học người Ba Lan Kazimierz Kuratowski, là một đặc tính của đồ thị phẳng.

Định lý 1

Đồ thị đủ K5 không phẳng.

Hình 1: Đồ thị đủ K5 không phẳng.

Định lý 2

Đồ thị lưỡng phân đủ K3,3 không phẳng.

Hình 2: Đồ thị lưỡng phân đủ K3,3 không phẳng.

• Nhận xét: hai đồ thị K5 và K3,3 là các đồ thị không phẳng đơn giản nhất với các tính chất sau

1. Nếu xóa đi 1 đỉnh hay 1 cạnh của 2 đồ thị trên thì chúng ta sẽ có được đồ thị phẳng.
2. Đồ thị K5 là đồ thị không phẳng có ít đỉnh nhất.
3. Đồ thị K3,3 là đồ thị không phẳng có ít cạnh nhất.

Định lý 3

• Điều kiện cần và đủ để một đồ thị liên thông G có tính phẳng là G không chứa bất kỳ đồ thị con nào đồng phôi với K5 hay K3,3.

Hình 3: Định lý 3