Question

求证一道离散数学题目

n个城市用k条公路的网络连结。一条公路定义为两个城市间的一条不穿过任何中间城市的道路。任意两个城市之间至多修一条公路。证明如果k> (n-1)(n-2)，则人们总能通过连结的公路，在任何两个城市间旅行。

Answer 1

题目抄错了吧，应该是证明“如果k>
(n-1)(n-2)/2，则人们总能通过连结的公路，在任何两个城市间旅行。”
证明如下：
顶点数为n-1的无向完全图的边数m=(n-1)(n-2)/2,
所以当一个图G具有n个节点，且边数m>(n-1)(n-2)/2时，图G为连通图。
题目得证。