作者jvvbn0601 (part2)
看板Prob_Solve
標題[問題] 用induction證明無向圖必有一點為non-cut
時間Wed Oct 30 21:14:06 2013
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
1F：推 LPH66:_△∠ 左邊應該是你的 2) 的反例: deg 3 那點拿掉照斷 10/30 23:40
2F：推 rebaudiana:2) 點雙連結？ 10/31 06:27
3F：→ rebaudiana:啊…沒事 10/31 06:28
4F：推 springman:若是沒有 cycle 的話，找一條最長的 path，它的兩個端點 11/03 17:01
5F：→ springman:都是 non-cut。就算是有 cycle，似乎也是如此。 11/03 17:02
6F：推 springman:證明應該很簡單，最長的 path 的端與不在 path 上的點 11/04 09:27
7F：→ springman:一定不相鄰，不然該 path 就不是最長的，所以是 non-cut 11/04 09:27
8F：→ springman:所謂的最長應該是 maximal length、不是 maximum length 11/04 09:33