HMMT 二月 2004 · COMB 赛 · 第 7 题

英文解析

7. We have a polyhedron such that an ant can walk from one vertex to another, travelingonly along edges, and traversing every edge exactly once. What is the smallest possibletotal number of vertices, edges, and faces of this polyhedron?
   Solution: 20
   This is obtainable by construction. Consider two tetrahedrons glued along a face; thisgives us 5 vertices, 9 edges, and 6 faces, for a total of 20, and one readily checks that the required Eulerian path exists. Now, to see that we cannot do better, first noticethat the number v of vertices is at least 5, since otherwise we must have a tetrahedron,
   which does not have an Eulerian path. Each vertex is incident to at least 3 edges, andin fact, since there is an Eulerian path, all except possibly two vertices are incident to 2
   an even number of edges. So the number of edges is at least (3 + 3 + 4 + 4 + 4) / 2 (sinceeach edge meets two vertices) = 9. Finally, if f = 4 then each face must be a triangle,
   because there are only 3 other faces for it to share edges with, and we are again in thecase of a tetrahedron, which is impossible; therefore f ≥ 5. So f + v + e ≥ 5+5+9 = 19.
   But since f + v − e = 2 − 2 g (where g is the number of holes in the polyhedron), f + v + emust be even. This strengthens our bound to 20 as needed.