簡單的說,就是沒有回路,必有葉子節(jié)點,與度不為1矛盾
復(fù)雜的說：
反證：如果G中不存在回路,則必有一個節(jié)點的度為1
可以說明：任意找一個節(jié)點,開始遍歷,那么最終會訪問到一個葉子節(jié)點.
任何一個訪問到的節(jié)點u,存在以下幾種情況
1. 是葉子節(jié)點（證明結(jié)束）
2. 存在節(jié)點v,v尚未被訪問,且邊(u,v)存在,則繼續(xù)訪問v
3. 任何與u有邊相連的節(jié)點都已經(jīng)被訪問,這種情況會構(gòu)成回路（與假設(shè)矛盾,證明結(jié)束）
因為節(jié)點個數(shù)有限,所以只有有限次可能會落入情況2,隨著遍歷的進(jìn)行,必然會落入情況1和3