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?
请问一下，我的观念是否有错?
还有如何用数学归纳法证明呢?

_△∠ 左边应该是你的 2) 的反例: deg 3 那点拿掉照断

2) 点双连结？啊…没事

若是没有 cycle 的话，找一条最长的 path，它的两个端点都是 non-cut。就算是有 cycle，似乎也是如此。证明应该很简单，最长的 path 的端与不在 path 上的点一定不相邻，不然该 path 就不是最长的，所以是 non-cut所谓的最长应该是 maximal length、不是 maximum length