PUMaC 2017 · 个人决赛（B 组） · 第 1 题

PUMaC 2017 — Individual Finals (Division B) — Problem 1

The Frontier Lands have 50 towns, some pairs of which are directly connected by Morton’s railroad tracks (which are bidirectional and may pass over each other), and it is possible to travel from any town to any other town via these tracks, possibly stopping at other towns on the way. Morton decides that he wants some tracks destroyed so that each town is directly connected to an odd number of other towns. (After Morton destroys the tracks, it might no longer be possible to travel from any town to any other town.) Prove that this is possible.

解析

We reformulate the question in graph-theoretic terms for conciseness. Given a connected graph G with an even number of vertices, we wish to show that there exists a subset of edges S such that each vertex is incident with an odd number of edges in S . Consider a spanning tree T of G . We claim that we can delete some edges from T such that the remaining edges satisfy the condition. If every vertex of T has odd degree, then we are done. Otherwise, there exists a vertex v of even degree in T . If the edges incident with v are e , . . . , e , then removing v splits T into connected components T , . . . , T , where the end of 1 2 n 1 2 n e other than v is inside T for each k . Then, since G has an even number of vertices, there k k must be some k such that T has an even number of vertices. If we remove e from T , then k k we can apply induction to the two resulting connected components, and the claim is proved. Problem written by Bill Huang