※ 引述《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里面那两个割点。
就证完了