※ 引述《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)