※ 引述《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. Read the condition more carefully.. You have a connected Graph G, and you want to prove there is at least a point v in G, such that G\v is connected.. 1. Because G is connected, we can always generate a Minimum-spanning tree (MST) for G. 2. Pick one leaf in MST, we call it v in G. 3. Now, the remaining G\v is still connected. Done. You need to work on some finer detail, but I think this works. -- 一箫一剑平生意 负尽狂名十五年 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 128.125.20.24