※ 引述《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裡面那兩個割點。
就證完了
--
用「有無cycle」、「有無degree = 1的點」來分類，似乎都不是很好證。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 36.225.182.249
※ 編輯: DJWS 來自: 36.225.182.249 (11/03 20:17)