附加题一：平面上n个点和若干条边所成的图不是哈密顿图，但若任意去掉一点及与之相连的边，则剩下的图为哈密顿图，求n的最小值。”
秦克倒抽了口凉气，不愧是国赛难度，上来就是哈密顿图。
哈密顿这个名字，估计全国九成九的高中生都没留意过。
哈密顿是十八世纪的英国著名数学家，当年他提出一个名为“环游世界”的游戏，用一个正十二面体的二十个顶点代表二十个大城市，要求沿着棱，从一个城市出发，只经过每个城市一次，然后回到出发点，这就是著名的“哈密顿问题”。
后来数学界将“经过图上各顶点一次并且仅仅一次的圈”称之为“哈密顿圈”，一个图如果包含哈密顿圈，那这个图就可以被称为“哈密顿图”。
从表面上来看，这个哈密顿问题似乎与欧拉的哥尼斯堡七桥问题（哥尼斯堡七桥问题是指，河中有两个岛，河上有七座桥连接这两个岛及河的两岸，请问能否通过每座桥一次且仅一次。它也被称为“一笔画”问题）非常相似，但两者有着本质的区别。
哥尼斯堡七桥问题已被欧拉自己解决了，并由此开创了数学的新分支——“图论”。
哈密顿问题却迄今为止都未曾解决，一百多年来无数一流的数学家费尽心思，也没找到判断它的充分必要条件，只是提出了一些已被证实的必要条件和充分条件，应用到不同的场合。
这道题目难就难在不但要求解题人了解哈密顿图的特
第六十三章 省赛开考！哈密顿图！(4/5)