MinDegreeSubgraph | Topcoder Archive

Problem Statement

All graphs in this problem are undirected simple graphs. (I.e., each pair of vertices is connected by at most one edge, and there are no loops.)

Let G=(V,E) be a graph. We call a graph H=(V',E') a subgraph of a graph G if the following conditions hold:

V' is a nonempty subset of V
E' is a subset of E
for each edge in E', both its endpoints are in V'

In other words, a subgraph can be constructed by first removing some vertices (possibly none, but not all of them) together with all their edges, and then removing some of the remaining edges (possibly none or all of them).

The mindegree of a graph is the minimum of the degrees of its vertices.

A graph is locally k-dense if it contains a subgraph with mindegree k.

You are given an int n, a long m, and an int k. Consider all graphs on n vertices with exactly m edges. Determine whether all, some, or none of these graphs are locally k-dense. Return "ALL", "SOME", or "NONE", respectively.

Definition

Class:: MinDegreeSubgraph
Method:: exists
Parameters:: int, long, int
Returns:: String
Method signature:: String exists(int n, long m, int k)
(be sure your method is public)

Notes

Given the constraints of the problem, there always exists at least one graph with n vertices and m edges.
Given a graph, the degree of a vertex is the number of edges incident with this vertex.
The return value "SOME" means that there exists a graph with the desired property and also a graph without the desired property.

Constraints

n will be between 1 and 109, inclusive.
m will be between 0 and n(n-1)/2, inclusive.
k will be between 0 and 109, inclusive.

Examples

```
3
```
```
3
```
```
2
```
```
Returns: "ALL"
```
Up to isomorphism, there is only one graph on 3 vertices and 3 edges: the triangle. It does have a subgraph with mindegree 2: itself. (Note that each graph is its own subgraph.)
```
4
```
```
3
```
```
2
```
```
Returns: "SOME"
```
Two of the graphs with 4 vertices and 3 edges are trees. Obviously, a tree cannot be locally 2-dense, because each subgraph of a tree is a forest, and each forest contains a vertex of degree at most 1. Another graph with 4 vertices and 3 edges is a graph that consists of a triangle and an isolated vertex. This graph is locally 2-dense because it contains a subgraph with mindegree 2: the triangle.
```
6
```
```
10
```
```
3
```
```
Returns: "ALL"
```
There are many graphs with 6 vertices and 10 edges. No matter which one of them we choose, it will always contain some subgraph with mindegree exactly 3.
```
6
```
```
15
```
```
4
```
```
Returns: "ALL"
```
There is only one such graph: the complete graph K6. It contains many mindegree-4 subgraphs. For instance, we can construct such a subgraph by removing any one vertex, and we can also construct a different mindegree-4 subgraph by removing any one edge.
```
17
```
```
53
```
```
11
```
```
Returns: "NONE"
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.