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 edgesso that each vertex still has at least half of its original degree.2
10
解析
英文解析
- [ 60 ] Evan has a simple graph with v vertices and e edges. Show that he can delete at least edgesso that each vertex still has at least half of its original degree.2
Proposed by: Allen Liu
Fix v . We use strong induction on the number of edges e . If e ≤ v − 1, the result trivially holds byremoving 0 edges. Now take e > v − 1 and assume the result has been shown for all smaller values ofe . 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 ande − 2 k − v +1
′
e − 2 k edges. By the inductive hypothesis, it is possible to remove edges from G so that each vertex still has at least half its original degree. In the original graph G , remove these same edges,2
and also remove every other edge of C (so, if the vertices of C are v , · · · , v in order, we remove the
1 2 ke − 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 haveany vertices or edges in common. Suppose the contrary; then two odd cycles overlap, so their union isconnected and has an even number of edges. This union has an Eulerian tour, which is a cycle withan 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 removee − v +1 cat 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 andso has degree at least 2. Therefore each vertex still has at least half of its original degree, and we havee − v +1
removed at least edges, as desired.
Thus our claim holds for a graph with e edges, and thus by induction holds for any number of edges,2
as needed.
10