推 springman:good 11/04 16:13
※ 引述《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