Câu hỏi lý thuyết đồ thị chứng minh

Question

Tôi không thể đưa ra bằng chứng về tuyên bố này -

Coi G là một đồ thị phẳng liên thông. Nếu G không phải là lưỡng cực thì bất kỳ phép nhúng phẳng nào của G đều có ít nhất 2 mặt có bậc lẻ.

Ai đó có thể giúp tôi với bằng chứng?

Answer 1

Vì G không phải là chất lưỡng tính nên G chứa chu kỳ lẻ C. Cho $F_{1},F_{2},......,F_{k}$là các mặt bên trong C trong phép nhúng phẳng. Hãy xem xét tổng các độ của những khuôn mặt này.

• Mỗi cạnh trong C được tính một lần.
• Gọi D là tập hợp các cạnh trên bất kỳ đường biên nào của bất kỳ $F_{i}$, nhưng không phải trên C.

Mỗi cạnh trong D được tính hai lần.

Vì thế $\sum_{i}$ $\deg(F_{i})$ = $|E(C)| + 2|D|$

Từ $|E(C)|$ kỳ quặc và $2|D|$ là thậm chí,

$\sum_{i}$ $\deg(F_{i})$ kỳ quặc, vì vậy $\deg(F_{i})$ phải là kỳ lạ đối với một số $i$

Vậy có ít nhất một mặt bên trong C có bậc lẻ.

Lập luận tương tự có thể được sử dụng để chỉ ra rằng ít nhất một lần mặt ngoài C có bậc lẻ.