HMMT 二月 2018 · 团队赛 · 第 9 题
HMMT February 2018 — Team Round — Problem 9
题目详情
- [ 60 ] Evan has a simple graph with v vertices and e edges. Show that he can delete at least edges 2 so that each vertex still has at least half of its original degree. 10
解析
- [ 60 ] Evan has a simple graph with v vertices and e edges. Show that he can delete at least edges 2 so that each vertex still has at least half of its original degree. Proposed by: Allen Liu Fix v . We use strong induction on the number of edges e . If e ≤ v − 1, the result trivially holds by removing 0 edges. Now take e > v − 1 and assume the result has been shown for all smaller values of e . Consider a graph G with v vertices and e edges. Suppose G contains a cycle C of even length 2 k , where vertices (but not edges) may be repeated in ′ ′ the cycle. Let G be the subgraph of G with the edges of C removed. Then G has v vertices and e − 2 k − v +1 ′ e − 2 k edges. By the inductive hypothesis, it is possible to remove edges from G so that 2 each vertex still has at least half its original degree. In the original graph G , remove these same edges, and also remove every other edge of C (so, if the vertices of C are v , · · · , v in order, we remove the 1 2 k e − 2 k − v +1 e − v +1 edges between v and v for 1 ≤ i ≤ k ). In total, we have removed + k = edges. 2 i − 1 2 i 2 2 Furthermore, all vertices in G still have at least half their original degrees, as desired. The remaining case to consider is if G has no cycles of even length. Then no two cycles in G can have any vertices or edges in common. Suppose the contrary; then two odd cycles overlap, so their union is connected and has an even number of edges. This union has an Eulerian tour, which is a cycle with an even number of edges, contradicting our assumption. The number of edges in G is at most v + c − 1, where c is the number of cycles. So, we must remove e − v +1 c at least = edges from G . But we can remove c edges from G , one from each cycle. No vertex 2 2 has its degree decreased by more than 1, and each vertex whose degree is decreased is in a cycle and so has degree at least 2. Therefore each vertex still has at least half of its original degree, and we have e − v +1 removed at least edges, as desired. 2 Thus our claim holds for a graph with e edges, and thus by induction holds for any number of edges, as needed. 10