某王国有16个城市。国王希望规划一个道路系统，使得任两城市间的道路互通所经过的中间城市不超过一个。还规定以每个城市为端点的路不超过5条。

　　（1）试证l所述要求可实现；

　　（2）试证：如果将数5换成4，那么所述要求不能实现。

　　解  （1）图1是实现所述要求的设计方案示意图。

　　为了不让太多的线路搅乱视线，在图中未画出以下10条道路

　　鉴于对称性，只需按以下三种情形分别验证即可。

　　（2）假设每个城市最多引出4条道路，并且任两城市可经过不多于一个中间城市的道路互通。首先观察图2，如果某个城市引出的道路不多于3条，那么从该城市出发，能按规定道路到达的城市，至多有12个。因此，从每一个城市引出的道路都有4条。

　　然后观察图3。如果某城市引出的道路有4条，并且该城市是某个道路三角形的顶点，那么从该城市出发能按规定到达的城市最多有14个。接着观察图4.我们看到，如果不存在三角形道路或四边形道路，那么至少有17个城市。图5告诉我们，如果某城市是两个道路四边形的顶点，那么总共至多有15个城市。因此，满足要求的道路网没有任何道路三角形，并且每个城市恰为一个道路四边形的顶点。

　　设道路网中两两无公共点四边形为A_jB_jC_jD_j；1≤j≤4.城市A1除了所在道路四边形的两条道路以外，另外还有两条道路引出，其中无一条通往C₁（否则将形成道路三角形）。这两条路也不能都通往第k个四边形（2≤k≤4），否则会出现道路三角形或者第5个道路四边形（使得某些点是两个道路四边形的顶点）。不妨设从A₁引出的另两条路当中，第一条通往A₂，第二条通往A₃。我们用（2，3）给A₁标号，表示有一条道路通向第2个道路四边形，另有一条道路通向第3个道路四边形。因为A1必须能经过至多一个中间城市到第4个道路四边形中的城市，所以A₂和A₃各有一条道路通往第4个道路四边形的两个城市。从B₁和D₁也各有一条道路通向第4个道路四边形的另外两个城市。不妨设B₁的标号为（2，4），D₁的标号为（3，4）。

　　请注意，B₂与D₁的标号不同，并且都与A₁的标号不同。由于对称性，三城市A₁，B₁，C₁的标号也各不相同。于是，C₁的标号只能是（3，4）。但这样C₁和D₁就会有同样的标号。矛盾！