※ 引述《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?
: 請問一下，我的觀念是否有錯?
: 還有如何用數學歸納法證明呢?
這命題還不夠強，不是很好證。
姑且改成「砍掉之後還是connected graph的點，至少有兩點。」
(1) 圖上只有兩點，顯然成立。
(2) 現在圖上嘗試增加一點，形成connected graph。
　　大致上可以分成這些情況：
　　x. 新點連著一個、兩個、三個、...的connected graph。
　　y. 連接的邊可以是一條、兩條、三條、...。
　　比較值得討論的情況就這四種：http://postimg.org/image/rc4ehhkzf/
　　1. 新點 + connected graph裡面沒被新點連到的那個割點。
　 2. 新點 + connected graph裡面那兩個割點。
　　3. 兩個connected graph裡面，沒被新點連到的割點，各一個。
4. 被兩條邊以上連到的coneected graph裡面那兩個割點。
就證完了