HMMT 二月 2020 · 冲刺赛 · 第 18 题
HMMT February 2020 — Guts Round — Problem 18
题目详情
英文原题
- [10] A vertex-induced subgraph is a subset of the vertices of a graph together with any edges whoseendpoints are both in this subset.
An undirected graph contains 10 nodes and m edges, with no loops or multiple edges. What is the minimum possible value of m such that this graph must contain a nonempty vertex-induced subgraphwhere all vertices have degree at least 5?
解析
英文解析
- [10] A vertex-induced subgraph is a subset of the vertices of a graph together with any edges whoseendpoints are both in this subset.
An undirected graph contains 10 nodes and m edges, with no loops or multiple edges. What is the minimum possible value of m such that this graph must contain a nonempty vertex-induced subgraphwhere all vertices have degree at least 5?
Proposed by: Benjamin Qi
Answer: 31
Solution: Suppose that we want to find the vertex-induced subgraph of maximum size where eachvertex has degree at least 5. To do so, we start with the entire graph and repeatedly remove any vertexwith degree less than 5.
If there are vertices left after this process terminates, then the subgraph induced by these verticesmust have all degrees at least 5 . Conversely, if there is a vertex-induced subgraph where all degrees areat least 5 , then none of these vertices can be removed during the removing process. Thus, there arevertices remaining after this process if and only if such a vertex-induced subgraph exists.
If the process ends with an empty graph, the largest possible number of edges are removed when the first 5 removed vertices all have 4 edges at the time of removal, and the last 5 vertices are all con-
nected to each other, resulting in 5 × 4+4+3+2+1+0 = 30 removed edges. The answer is 30+1 = 31.