10个,参考图论Hamilton
9条线路可走遍所有车站,说明图中有N个点(未知),通常9条边连通
任何8条线路不能走遍所有车站,则图论中的定理,可推知这9条边是连通图的Hamilton路,(这个定理相当有深度呃,自己证当然缺德了咯)
9条边的Hamilton路共10个顶点
或者(这个可能浅一点):
有9条边,说明图中至多10个顶点连通(即10个车站),以9条边及相应端点可排列出一条链路(v1,e12,v2,e23,v3...)(v是点,e为边)
现在用反证法
如果图中少于10个顶点,说明图中有圈,(圈的概念是链路的起点和终点相同,比如说(v1,e12,v2,e23,v3,e31,v1)).
我们知道,在圈中删去任一边,图仍然保持连通(可到达)
所以如果图中有圈的话,可删去圈中任一边成为8条路,仍连通(可到达),与题目矛盾
所以图中恰有10顶点