作者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