Định lýĐã chứng minh

Định lý Kuratowski

Phát biểu

Một đồ thị hữu hạn là phẳng khi và chỉ khi nó không chứa một đồ thị con là phép phân chia của $K_5$ (đồ thị đầy đủ trên 5 đỉnh) hoặc $K_{3,3}$ (đồ thị hai phía đầy đủ trên $3+3$ đỉnh).

Vì sao đúng?

Mọi sự thất bại của tính phẳng đều quy về một trong hai mớ rối tối tiểu — năm đỉnh nối đôi một với nhau ( $K_5$ ), hoặc ba trạm tiện ích nối với ba ngôi nhà ( $K_{3,3}$ ) — có thể được ngụy trang bởi các đỉnh bậc 2 chèn thêm dọc theo các cạnh của chúng. Nếu không có lõi không phẳng tối tiểu nào trong hai lõi đó ẩn bên trong đồ thị, thì đồ thị luôn vẽ được trên mặt phẳng mà không có cạnh cắt nhau.

Phác thảo chứng minh

Việc $K_5$ và $K_{3,3}$ (và do đó các phép phân chia của chúng) không phẳng suy ra từ công thức Euler $V - E + F = 2$ : một đồ thị phẳng trên $V \ge 3$ đỉnh thỏa mãn $E \le 3V - 6$ (loại trừ $K_5$ , có $V=5, E=10$ ) và $E \le 2V - 4$ nếu không có tam giác (loại trừ $K_{3,3}$ , là đồ thị hai phía với $V=6, E=9$ ). Cho chiều ngược lại, xét một phản ví dụ không phẳng tối tiểu $G$ , chứng minh nó 3-liên thông, co hoặc xóa một cạnh $e = \{u,v\}$ rồi phân tích cách các đường đi quanh các mặt của phép nhúng phẳng của $G - e$ cản trở việc đặt $e$ không cắt nhau, từ đó buộc phải xuất hiện một phép phân chia của $K_5$ hoặc $K_{3,3}$ .

Chủ đề chứa định lý này

Đồ thị phẳng Đồ thị, bậc, đường đi

Định lý liên quan

Công thức đa diện Euler

Chứng minh từng bước

Chưa có chứng minh từng bước cho định lý này.

Tài liệu tham khảo

Casimir Kuratowski (1930). Sur le problème des courbes gauches en Topologie