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

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为连通图.
题目得证.