[圖論] Hamiltonian的證明

[mqazz1 (無法顯示)]

Let G be a planar Hamiltonian simple graph with n vertices

Let C be a Hamiltonian cycle in G

Then with respect to C, prove Σ(k-2)(rk-sk) = 0

Here rk is the number of faces inside C whose boundary contain exactly k edges

sk is the number of faces outside C whose boundary contains exactly k edges



原始: http://ppt.cc/(6W,


請問這題要怎麼證呢?

謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 61.228.27.164
推 hcsoso      :這就是上次說的 Grinberg 定理. 用 Euler formula!