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 edges, with no loops or multiple edges. What is the minimum possible value of such that this graph must contain a nonempty vertex-induced subgraph where all vertices have degree at least 5?
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 connected to each other, resulting in removed edges. The answer is .
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.