Đường đi trong khối đa diện lồi

[man1995]

Mỗi cạnh của khối đa diện lồi được quy định 1 chiều sao cho tại mỗi đỉnh có ít nhất 1 cạnh đi vào và 1 cạnh đi ra khỏi nó .Hãy chứng minh rằng tồn tại hai mặt khác nhau của khối đa diện này sao cho trên mỗi mặt chiều đi của các cạnh kế tiếp nhau để ta có thể đi một vòng trên dường biên của nó theo chiều đi được quy định của các cạnh.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[beyondinfinity]

Gọi $v $, $e $, $f $, $V $, $F $ lần lượt là số đỉnh, cạnh, mặt, tập đỉnh, tập mặt của đa diện lồi.
Ta gọi một cặp cạnh tốt là 2 cạnh có chung 1 đỉnh sao cho một cạnh đi vào đỉnh đó và cạnh kia đi ra.
Ta có các nhận xét sau:
NX 1 (Euler): $v-e+f=2 $.
NX 2: Nếu một mặt là $k $-giác không có các mũi tên đi theo cùng một chiều thì số các cặp cạnh tốt trên mặt đó tối đa là $(k-2) $, nếu ngược lại thì số cặp cạnh tốt là $k $.
NX 3: tất cả các đỉnh trên đa diện lồi đều là đầu mút của ít nhất 3 cạnh.
Trở lại bài toán:
Giả sử phản chứng, có không quá 1 mặt mà các mũi tên đi cùng chiều.
Với một đỉnh $A $ có $r $ cạnh vào và $s $ cạnh ra, nó sẽ có $r\times s $ cặp cạnh tốt, như vậy, nó có ít nhất là $(\deg A -1) $ cặp cạnh tốt (do $r $ và $s $ $> 0 $).
Ta có đánh giá với số cặp cạnh tốt $S $ như sau:
$S\ge \sum_{A\in V}{(deg A-1)}=2e-v $.
Ngoài ra, ta đánh giá theo mỗi mặt:
$S\leq \sum_{f\in F} (e_f-2)+2 =2e-2f+2 $
($e_f $ là số cạnh của mặt $f $).
Vậy suy ra: $v+2 \ge 2f $.
Theo NX1, ta đưa về: $2e+2 \leq 3v $.
Tuy nhiên, do NX 3: $2e=\sum_{A\in V}\deg A \ge 3v $ nên ta có mâu thuẫn.
Cm kết thúc.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]