※ 引述《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?
: 请问一下，我的观念是否有错?
: 还有如何用数学归纳法证明呢?
有 cycle 也不见得可以从 cycle 拔，例如三个点组成三角形，下面连另外两
个点，变成 "A" 的形状，中间的两个点一拔就断了。
我的做法不使用数学归纳法，参考一下。很久没做题目了，希望没错。
先在图中任取一点 v0，然后对所有其他点，计算到达 v0 的最短路径，直接
相连的邻居就是 1，邻居的邻居为 2，以此类推。全部算完之后，随便挑一个离
v0 最远的 v，把它拔掉即可。v0 必然仍然和所有的点连通，若有一点 v' 因为
拔掉 v 而不再和 v0 相连，那么 v 必然在 v0 到 v' 的所有路径上，包括最短
路径，这与 v 是离 v0 最远的点矛盾，因此 v0 和所有的点连通。任两点也可
经过 v0 互相连通，因此整个图仍为连通。