题目

N个城市间有K条相互连接的真达公路.证明：当K>(N-1)(N-2)/2时,人们便能通过这些公路在任何两个城市间旅行.

提问时间：2020-11-03

答案

转化为图论问题既是：
在一个N顶点的无向图中,当边数K>(N-1)(N-2)/2时,证明其为连通图,证明如下：
假设存在一个N节点K条边无向图,为不连通的,即设它存在2个连通分支（连通分支越多,边数越少,故只需讨论两个连通分支的情况）,并设一个连通分支的节点数为S,则另一个连通分支为N-S,则易知：在这个图中,边数最大条数为
(S-1)(S)/2+（N-S)(N-S-1)/2,（每一个连通分支为完全图）,整理得,边数最大为：N×N-(2S+1)+S×S(S>=1),而K>(N-1)(N-2)/2=N×N-3N+2>=N×N-(2S+1)+S×S,故,在这两个连通分支之间必存在边,结论得证.