※ 引述《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?
: 請問一下，我的觀念是否有錯?
: 還有如何用數學歸納法證明呢?
有 cycle 也不見得可以從 cycle 拔，例如三個點組成三角形，下面連另外兩
個點，變成 "A" 的形狀，中間的兩個點一拔就斷了。
我的做法不使用數學歸納法，參考一下。很久沒做題目了，希望沒錯。
先在圖中任取一點 v0，然後對所有其他點，計算到達 v0 的最短路徑，直接
相連的鄰居就是 1，鄰居的鄰居為 2，以此類推。全部算完之後，隨便挑一個離
v0 最遠的 v，把它拔掉即可。v0 必然仍然和所有的點連通，若有一點 v' 因為
拔掉 v 而不再和 v0 相連，那麼 v 必然在 v0 到 v' 的所有路徑上，包括最短
路徑，這與 v 是離 v0 最遠的點矛盾，因此 v0 和所有的點連通。任兩點也可
經過 v0 互相連通，因此整個圖仍為連通。