Đồ thị phẳng

Đẳng thức duy nhất này là nguồn gốc của gần như mọi sự kiện khác về đồ thị phẳng, bao gồm chặn số cạnh và tính không phẳng của $K_5$ và $K_{3,3}$, và nó được chứng minh bằng một phép quy nạp ngắn gọn, hoàn toàn sơ cấp.

Cơ sở quy nạp. Nếu $E$ $= 0$ và đồ thị liên thông, nó phải chỉ gồm một đỉnh duy nhất ($V=1$), và có đúng một mặt, toàn bộ mặt phẳng không bị chặn ($F=1$). Khi đó $1 - 0 + 1 = 2$ đúng.

Bước quy nạp, trường hợp 1: một cạnh nằm trên chu trình. Giả sử công thức đúng với mọi đồ thị phẳng liên thông đã vẽ có ít hơn $E$ cạnh, và cho đồ thị có $E$ $\ge 1$ cạnh. Nếu một cạnh $e$ nằm trên chu trình, thì bỏ $e$ vẫn giữ đồ thị liên thông (phần còn lại của chu trình vẫn nối hai đầu mút của nó). Bỏ $e$ nhập hai mặt ở hai phía của nó thành một mặt duy nhất, nên đồ thị nhỏ hơn có $V$ đỉnh, $E - 1$ cạnh và $F - 1$ mặt. Theo giả thiết quy nạp, $V - (E-1) + (F-1) = 2$, rút gọn thành $V - E + F = 2$.

Bước quy nạp, trường hợp 2: không cạnh nào nằm trên chu trình. Khi đó mọi cạnh đều là cầu, nghĩa là đồ thị hoàn toàn không có chu trình, tức nó là một cây. Một cây vẽ trên mặt phẳng có đúng một mặt ($F = 1$, miền không bị chặn duy nhất, vì không có chu trình nào để bao một miền bị chặn), và một sự kiện chuẩn về cây là cây có $V$ đỉnh thì có đúng $E = V - 1$ cạnh. Thay vào, $V - E + F = V - (V - 1) + 1 = 2$.

Kết luận. Mọi trường hợp đều quy về công thức đúng, hoặc quy về (qua việc bỏ một cạnh) một đồ thị nhỏ hơn nơi nó đúng theo quy nạp, nên $V - E + F = 2$ với mọi đồ thị phẳng liên thông đã vẽ.

Điều này cho một đặc trưng đầy đủ, kiểm tra được của tính phẳng chỉ thông qua hai mẫu cấm nhỏ, biến một câu hỏi tồn tại (liệu ta có tìm được một cách vẽ không cắt nhau nào không?) thành việc tìm một trong hai vật cản cụ thể.

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 đủ.