題組內容

二、一個簡單圖（simple graph）是指此圖的每一個邊（edge）都是連接不同的兩點 （vertex），而且任意兩點之間最多只有一個邊相連。一個點 v 的度數（degree）就是有幾 個邊以 v 為頂點。令 G 為一個簡單圖，δ>0 為 G 中最小的點度數（minimum degree）， 亦即每個點的度數至少是 δ。

1證明：G 包含一個簡單路徑（simple path）其長度至少為 δ。（10 分）