返回题库

HMMT 二月 2018 · 团队赛 · 第 9 题

HMMT February 2018 — Team Round — Problem 9

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. [ 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
解析

英文解析

  1. [ 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