HMMT 二月 2004 · COMB 赛 · 第 7 题

HMMT February 2004 — COMB Round — Problem 7

We have a polyhedron such that an ant can walk from one vertex to another, traveling only along edges, and traversing every edge exactly once. What is the smallest possible total number of vertices, edges, and faces of this polyhedron?

解析

We have a polyhedron such that an ant can walk from one vertex to another, traveling only along edges, and traversing every edge exactly once. What is the smallest possible total number of vertices, edges, and faces of this polyhedron? Solution: 20 This is obtainable by construction. Consider two tetrahedrons glued along a face; this gives 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 notice that 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, and 2 in fact, since there is an Eulerian path, all except possibly two vertices are incident to an even number of edges. So the number of edges is at least (3 + 3 + 4 + 4 + 4) / 2 (since each 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 the case 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 + e must be even. This strengthens our bound to 20 as needed.