d-dimensional hypercube
點集可以想成{(a_1,a_2,...a_d): a_i = 0 or 1}
而兩個點(a_1,a_2,...,a_d)與(b_1,b_2,...b_d)相連的條件是"恰有一個位置不同".
從某一個起點出發，不失一般性假設為(0,0,...,0)
每走一步恰好只會改變一個位置（0 -> 1, 1 -> 0）
可以觀察奇數步時，此d維向量加起來是奇數；偶數步時，加起來為偶數。
因為最後要回到原點，故不可能有odd cycle存在！
以上是直接證法，但是若知道hypercube是bipartite graph，
又bipartite graph中沒有subgraph isomorphic to odd cycle，也可以得知！
※ 引述《awpboom (吃屎近乎勇)》之銘言：
: A cycle in a graph is defined as a path originating and terminating at the
: same node. The length of a cycle is the number of edges in the cycle. Show
: that there are no odd-length cycles in a d-dimensional hypercube
: 題目是這樣的
: 目前以微微薄的知識想說可以用Euler circuit 的定義來證
: 有歐拉迴路的充分且必要條件是要為連通圖，而且每個頂點的度數都是偶數。
: 但是現在只是個想法
: 但是如果要用成數學的是著證明該怎麼下手呢???
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.51.119
※ 編輯: over 來自: 140.112.51.119 (10/27 17:31)