Định lý Kuratowski

Vì sao chính $K_5$ và $K_{3,3}$ không phẳng. $K_5$ có $V=5$ đỉnh và $E=10$ cạnh, nhưng chặn cạnh $E \le 3V - 6$ đòi hỏi $10 \le 3(5)-6=9$, mâu thuẫn, nên $K_5$ không phẳng. $K_{3,3}$ là lưỡng phân với $V=6$ đỉnh và $E=9$ cạnh; một đồ thị lưỡng phân phẳng phải thỏa chặn chặt hơn $E \le 2V - 4$, đòi hỏi $9 \le 2(6)-4=8$, lại mâu thuẫn, nên $K_{3,3}$ cũng không phẳng.

Phép chia nhỏ giữ nguyên tính không phẳng (chiều dễ). Nếu một đồ thị $H$ là phép chia nhỏ của một đồ thị $G$ (mỗi cạnh của $G$ được thay bằng một đường đi rời nhau ở phần trong), và $G$ không phẳng, thì $H$ cũng không thể phẳng: mọi hình vẽ không cắt nhau của $H$ đều có thể biến thành một hình vẽ của $G$ chỉ bằng cách xóa các đỉnh bậc 2 bên trong mỗi đường đi và duỗi thẳng nó lại thành một cạnh duy nhất, việc này không tạo thêm chỗ cắt nhau nào. Vậy mọi đồ thị chứa một phép chia nhỏ của $K_5$ hoặc $K_{3,3}$ như đồ thị con đều tự động không phẳng, chứng minh chiều chỉ-khi của định lý.

Chiều ngược lại (chiều khó), phác thảo. Việc mọi đồ thị không phẳng đều phải chứa một phép chia nhỏ như vậy là phần sâu sắc, được Kuratowski chứng minh năm 1930 và, ở dạng tương đương dùng đồ thị con thu gọn, được Wagner chứng minh năm 1937. Lập luận tiến hành bằng cách lấy một đồ thị không phẳng nhỏ nhất giả định không chứa phép chia nhỏ nào của $K_5$ hay $K_{3,3}$ rồi suy ra mâu thuẫn: dùng định lý Menger về tính liên thông, trước tiên quy về trường hợp đồ thị liên thông 3 (đồ thị có một lát cắt đỉnh nhỏ có thể tách theo lát cắt đó thành các mảnh phẳng hoặc nhỏ hơn rồi ghép lại), rồi chỉ ra trực tiếp rằng mọi đồ thị không phẳng liên thông 3 có kích thước nhỏ nhất đã chứa một trong hai phép chia nhỏ bị cấm. Phép quy giản cấu trúc qua tính liên thông này chính là chỗ khó thật sự của định lý.

Kết luận. Kết hợp cả hai chiều, một đồ thị phẳng đúng khi nó tránh được cả hai phép chia nhỏ bị cấm, cho ta đặc trưng đầy đủ.