[問題] 用induction證明無向圖必有一點為non-cut

[jvvbn0601 (part2)]

For an undirected graph G=(V, E) and a vertex v in V, let G\v denote the
subgraph of G obtained by removing v and all the edges incident to v from G. If G is
connected, then G\v can be connected or disconnected. Prove that for any connected graph G,
we can always find a vertex v in G such that G\v is connected.

目前我的想法是1)沒有迴圈:視為樹，leaf必定是non-cut
              2)有迴圈:有迴圈的話，degree不是最大的應該都可以是non-cut?

請問一下，我的觀念是否有錯?
還有如何用數學歸納法證明呢?




--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 1.160.42.4
推 LPH66:_△∠ 左邊應該是你的 2) 的反例: deg 3 那點拿掉照斷
推 rebaudiana:2) 點雙連結？
→ rebaudiana:啊…沒事
推 springman:若是沒有 cycle 的話，找一條最長的 path，它的兩個端點
→ springman:都是 non-cut。就算是有 cycle，似乎也是如此。
推 springman:證明應該很簡單，最長的 path 的端與不在 path 上的點
→ springman:一定不相鄰，不然該 path 就不是最長的，所以是 non-cut
→ springman:所謂的最長應該是 maximal length、不是 maximum length