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 whose endpoints 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 subgraph where 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 whose endpoints 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 subgraph where 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 each vertex has degree at least 5. To do so, we start with the entire graph and repeatedly remove any vertex with degree less than 5. If there are vertices left after this process terminates, then the subgraph induced by these vertices must have all degrees at least 5 . Conversely, if there is a vertex-induced subgraph where all degrees are at least 5 , then none of these vertices can be removed during the removing process. Thus, there are vertices 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.