Đị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ý 1Sửa đổi

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

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

Định lý 2Sửa đổi

Đồ 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ý 3Sửa đổi

  • Đ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

Chú thíchSửa đổi

Tham khảoSửa đổi