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?
請問一下，我的觀念是否有錯?
還有如何用數學歸納法證明呢?

_△∠ 左邊應該是你的 2) 的反例: deg 3 那點拿掉照斷

2) 點雙連結？啊…沒事

若是沒有 cycle 的話，找一條最長的 path，它的兩個端點都是 non-cut。就算是有 cycle，似乎也是如此。證明應該很簡單，最長的 path 的端與不在 path 上的點一定不相鄰，不然該 path 就不是最長的，所以是 non-cut所謂的最長應該是 maximal length、不是 maximum length