怎样证明一个网络结构中如果有 n 个节点，则每个节点至少要有 n/2 个链路才能使得所有节点被连结？

[tesorouo]

[kizunai]

我感觉……每个节点至少有 1 个链路即可
不妨令一个节点为父节点，其余 n-1 个节点只需要有一个链路链接到父节点就可以让所有节点被链接了。
是我没有理解对题目吗？

[hahiru]

欧拉把问题的实质归于一笔画问题，即判断一个图是否能够遍历完所有的边而没有重复，而柯尼斯堡七桥问题则是一笔画问题的一个具体情境。欧拉最后给出任意一种河──桥图能否全部走一次的判定法则，从而解决了“一笔画问题”。对于一个给定的连通图，如果存在超过两个（不包括两个）奇顶点，那么满足要求的路线便不存在了，且有 n 个奇顶点的图至少需要 n/2 笔画出。如果只有两个奇顶点，则可从其中任何一地出发完成一笔画。若所有点均为偶顶点，则从任何一点出发，所求的路线都能实现，他还说明了怎样快速找到所要求的路线。

[WorldHi]

@kizunai 应该是不允许设计线路，感觉证明方式跟抽屉原理相似吧 大于 n/2 保证了任意两个相连节点要么直连或者存在公共节点同时和这两个节点相连

[tesorouo]

@WorldHi 我觉着你应该在正确的路上，应该是通过 GPHP 证明的