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

Khi cộng các bậc, mỗi cạnh được đếm đúng hai lần: một lần từ mỗi đầu mút. Vì vậy tổng là số chẵn; các đỉnh bậc chẵn đã đóng góp một lượng chẵn vào tổng, nên số đỉnh bậc lẻ phải là số chẵn.

Xét một đồ thị hữu hạn bất kỳ $G = (V, E)$. Xây dựng tập mọi cặp liên thuộc đỉnh-cạnh $(v, e)$ với đỉnh $v$ là đầu mút của cạnh $e$, rồi đếm tập này theo hai cách. Đếm theo đỉnh: mỗi đỉnh $v$ đóng góp đúng $\deg(v)$ cặp liên thuộc (một cặp cho mỗi cạnh chạm vào nó), nên tổng số là $\sum_{v \in V} \deg(v)$. Đếm theo cạnh: mỗi cạnh $e = \{u, w\}$ có đúng $2$ đầu mút, $u$ và $w$, nên nó đóng góp đúng $2$ cặp liên thuộc, và cộng trên toàn bộ $|E|$ cạnh cho $2|E|$.

Vì cả hai cách đếm đều đếm cùng một tập cặp, chúng phải bằng nhau: $\sum_{v \in V} \deg(v) = 2|E|$. Với khẳng định thứ hai, tách tổng thành các đỉnh bậc chẵn và bậc lẻ: $\sum_{v \text{ even}} \deg(v)$ là tổng các số chẵn, nên là số chẵn, do đó $\sum_{v \text{ odd}} \deg(v)$ cũng phải là số chẵn (vì tổng toàn phần $2|E|$ là số chẵn). Một tổng các số lẻ chỉ chẵn khi có một số chẵn số hạng, nên số đỉnh bậc lẻ $O$ là số chẵn.

Đi theo một vết bất kỳ; mỗi lần đi qua một đỉnh (không phải điểm đầu/cuối) ta dùng hết hai cạnh của nó, nên một đỉnh có thể bị 'kẹt lại' (trừ hai đầu mút) phải có bậc chẵn — đây là chiều dễ. Chiều ngược lại (bậc chẵn là đủ) được chứng minh bằng quy nạp: tách ra các chu trình con khép kín rồi ghép chúng lại (cách dựng của Hierholzer, 1873).

(Chiều cần thiết.) Giả sử một đồ thị liên thông $G$ có chu trình Euler $C$, tức một vết khép kín dùng mọi cạnh đúng một lần. Mỗi lần $C$ đi qua một đỉnh $v$ khác đỉnh đầu/cuối, nó đi vào theo một cạnh rồi đi ra theo một cạnh khác chưa dùng, tiêu thụ đúng $2$ cạnh kề của $v$; vì $C$ dùng mọi cạnh của $v$ đúng một lần khi kết thúc, $\deg(v)$ phải là số chẵn với mọi đỉnh, kể cả đỉnh đầu/cuối, nơi cạnh khởi hành đầu tiên ghép cặp với cạnh đến cuối cùng.

(Chiều đủ.) Giả sử ngược lại mọi đỉnh của đồ thị liên thông $G$ đều có bậc chẵn. Bắt đầu tại một đỉnh bất kỳ và đi tham lam theo các cạnh chưa dùng; vì mọi đỉnh có bậc chẵn, mỗi khi đường đi vào một đỉnh khác đỉnh xuất phát, nó luôn có thể đi ra tiếp (một số chẵn cạnh kề không bao giờ có thể giảm còn đúng $1$ cạnh chưa dùng), nên đường đi chỉ có thể bị kẹt khi quay lại đỉnh xuất phát, tạo ra một vết khép kín $C$. Nếu $C$ đã dùng mọi cạnh, ta xong. Nếu không, vì $G$ liên thông, có một đỉnh $v$ trên $C$ có cạnh kề chưa dùng; các cạnh chưa dùng cũng có bậc chẵn tại mọi đỉnh (bỏ vết khép kín bậc chẵn $C$ vẫn giữ nguyên tính chẵn lẻ), nên theo lập luận tương tự chúng tạo thành một vết khép kín khác $C'$ qua $v$. Ghép $C'$ vào $C$ tại $v$ tạo ra một vết khép kín dài hơn; lặp lại quá trình ghép này (cách dựng của Hierholzer, 1873) cho tới khi không còn cạnh chưa dùng sẽ cho ra một chu trình Euler.

Nếu có tập $S$ với $|N(S)| < |S|$, các đỉnh của $S$ không có đủ đỉnh lân cận để ghép cặp một-một, nên điều kiện là cần thiết rõ ràng. Điều kiện này cũng đủ, được chứng minh bằng cách tìm đường tăng cường mỗi khi phép ghép cặp chưa hoàn chỉnh (lập luận đường tăng cường König–Egerváry).

(Chiều cần thiết.) Nếu có $S \subseteq X$ với $|N(S)| < |S|$, thì các đỉnh của $S$ có ít hơn $|S|$ đối tác khả dĩ trong toàn bộ $Y$ cộng lại, nên không phép ghép cặp nào có thể đưa $S$ vào $Y$ một cách đơn ánh — do đó không thể tồn tại phép ghép cặp phủ hết $X$. Vậy điều kiện Hall $|N(S)| \ge |S|$ rõ ràng là cần thiết.

(Chiều đủ.) Giả sử điều kiện Hall đúng nhưng có một phép ghép cặp $M$ để lại một đỉnh $x_0 \in X$ chưa ghép. Xây cây luân phiên từ $x_0$: đi theo các cạnh không thuộc ghép cặp ra khỏi đỉnh $X$ rồi các cạnh thuộc ghép cặp quay lại từ đỉnh $Y$, khám phá mọi đỉnh có thể đến được bằng cách này. Nếu cây này đến được một đỉnh $Y$ là $y$ chưa được $M$ phủ, đường đi từ $x_0$ đến $y$ luân phiên cạnh không-thuộc/thuộc ghép cặp và có độ dài lẻ, nên hoán đổi các cạnh đã ghép và chưa ghép dọc theo nó (lấy hiệu đối xứng $M \triangle P$) làm tăng chặt số cặp ghép lên một, mâu thuẫn với việc $M$ đã lớn nhất có thể theo nhánh này — lặp lại cho tới khi không còn $x_0$ chưa ghép, hoặc điều kiện Hall bị vi phạm trên tập $S$ các đỉnh $X$ đã đến được, vì khi đó mọi đỉnh $Y$ đến được đều được ghép ngược vào $S$, buộc $|N(S)| \le |S| - 1$. Vì điều kiện Hall đúng theo giả thiết, mâu thuẫn này không thể xảy ra, nên mọi đỉnh của $X$ cuối cùng đều phải được ghép cặp — đây chính là lập luận đường tăng cường König–Egerváry.

$K_5$ và $K_{3,3}$ tự chúng không phẳng (có thể kiểm tra trực tiếp bằng công thức Euler $V - E + F = 2$), và bất kỳ phép chia cạnh nào (thay cạnh bằng đường đi) cũng giữ nguyên tính không phẳng. Định lý Kuratowski năm 1930 là chiều ngược lại đáng ngạc nhiên: hai đồ thị này là những 'vật cản' duy nhất.

(Chiều cần: $K_5$, $K_{3,3}$ và các phép chia cạnh của chúng đều không phẳng.) Trong mọi đồ thị đơn phẳng liên thông có $V \ge 3$ được vẽ không cắt nhau, mỗi miền mặt $F$ được bao bởi ít nhất $3$ cạnh và mỗi cạnh tiếp giáp tối đa $2$ mặt, nên đếm số cặp liên thuộc cạnh-mặt cho $2E \ge 3F$. Thay $F = E - V + 2$ từ công thức Euler $V - E + F = 2$ cho $2E \ge 3(E - V + 2)$, tức $E \le 3V - 6$. Với $K_5$ ta có $V = 5$ và $E = 10$, vi phạm $3V - 6 = 9 < 10$, nên $K_5$ không phẳng. Với đồ thị hai phía $K_{3,3}$, không có chu trình lẻ (do đó không có tam giác), nên mỗi mặt cần ít nhất $4$ cạnh: $2E \ge 4F$, kết hợp với $V - E + F = 2$ cho $E \le 2V - 4$. Vì $K_{3,3}$ có $V = 6$ và $E = 9$, vi phạm $2V - 4 = 8 < 9$, nên $K_{3,3}$ cũng không phẳng.

Chia nhỏ một cạnh (thay nó bằng một đường đi qua các đỉnh mới bậc $2$) không ảnh hưởng tới việc đồ thị có vẽ được trên mặt phẳng không cắt nhau hay không, nên mọi đồ thị chứa một phép chia cạnh của $K_5$ hoặc $K_{3,3}$ đều không phẳng. Với chiều ngược lại (chiều đủ), do Kuratowski chứng minh năm 1930, ta quy nạp theo $|V| + |E|$: một đồ thị không phẳng tối tiểu $G$ phải $3$-liên thông, và khi xóa một cạnh $e$ sẽ tạo ra đồ thị phẳng $G - e$ mà chu trình bao quanh hai đầu mút của $e$ có các dây cung đan xen cả bên trong lẫn bên ngoài, buộc phải xuất hiện một phép chia cạnh của $K_5$ hoặc $K_{3,3}$ bên trong $G$.