文档介绍：王国之路
某王国有 16 个城市。国王希望规划一个道路系统，使得任两城市间的道路
互通所经过的中间城市不超过一个。还规定以每个城市为端点的路不超过 5 条。
王国之路
某王国有 16 个城市。国王希望规划一个道路系统，使得任两城市间的道路
互通所经过的中间城市不超过一个。还规定以每个城市为端点的路不超过 5 条。
（1）试证 l 所述要求可实现；
（2）试证：如果将数 5 换成 4，那么所述要求不能实现。
解（1）图 1 是实现所述要求的设计方案示意图。
为了不让太多的线路搅乱视线，在图中未画出以下 10 条道路
鉴于对称性，只需按以下三种情形分别验证即可。
（2）假设每个城市最多引出 4 条道路，并且任两城市可经过不多于一个中
间城市的道路互通。首先观察图 2，如果某个城市引出的道路不多于 3 条，那么
从该城市出发，能按规定道路到达的城市，至多有 12 个。因此，从每一个城市
引出的道路都有 4 条。
然后观察图 3。如果某城市引出的道路有 4 条，并且该城市是某个道路三角
形的顶点，那么从该城市出发能按规定到达的城市最多有 14 个。接着观察图 ，如果不存在三角形道路或四边形道路，那么至少有 17 个城市。图 5
告诉我们，如果某城市是两个道路四边形的顶点，那么总共至多有 15 个城市。
因此，满足要求的道路网没有任何道路三角形，并且每个城市恰为一个道路四边
形的顶点。
设道路网中两两无公共点四边形为 A B C D ；1≤j≤ A1 除了所在道路
j j j j
四边形的两条道路以外，另外还有两条道路引出，其中无一条通往 C（否则将形
1
成道路三角形）。这两条路也不能都通往第 k 个四边形（2≤k≤4），否则会出
现道路三角形或者第 5 个道路四边形（使得某些点是两个道路四边形的顶点）。
不妨设从 A 引出的另两条路当中，第一条通往 A ，第二条通往 A 。我们用（2，
1 2 3
3）给 A 标号，表示有一条道路