Codeforces #236 Div2

Question

Let's call an undirected graph of n vertices p-interesting, if the following conditions fulfill:

1. the graph contains exactly 2n + p edges;
2. the graph doesn't contain self-loops and multiple edges;
3. for any integer k (1 ≤ k ≤ n), any subgraph consisting of k vertices contains at most 2k + p edges.

A subgraph of a graph is some set of the graph vertices and some set of the graph edges. At that, the set of edges must meet the condition: both ends of each edge from the set must belong to the chosen set of vertices.

The task is to find a p-interesting graph consisting of n vertices.

To see the problem statement click here

I can not even understand the tutorial explained here.

If anyone can point me to the theory required for the background or some obscure theorem related to this problem. I'd be very glad.

Answer 1

That's a somewhat muddled editorial. Let's focus on creating 0-interesting graphs first. The key fact from graph theory is the following formula.

sum_{vertices v} degree(v) = 2 #edges

In a graph where every vertex has degree 4 (4-regular graph), the left-hand side is 4n, so the number of edges is exactly 2n. Every n'-vertex subgraph of a 4-regular graph has vertices of degree at most 4, so the left-hand side is at most 4n', and the number of edges is at most 2n'. Thus, every 4-regular graph is 0-interesting. There are many ways to obtain a 4-regular graph; one is to connect vertex i to vertices i - 2, i - 1, i + 1, i + 2 modulo n.

Assuming that n >= 5, the editorial aims to prove that a graph comprised of edges (1, v) and (2, v) for all v from 3 to n and (1, 2) is "(-3)-interesting", which technically doesn't work out because each 1-vertex subgraph should have at most 2(1) - 3 = -1 edges (oops). Since the actual p of interest are nonnegative and there are no self-loops, though, this problem will resolve itself when we add the additional edges as below. For n'-vertex subgraphs with n' >= 2, we consider four cases, two of which are symmetric. The first case is that the subgraph includes neither 1 nor 2. This subgraph has no edges, and n' >= 2 implies that 0 < 2n' - 3. The second case is that the subgraph includes 1 but not 2. This subgraph can have edges from 1 to each of its other vertices, at most n' - 1 <= 2n' - 3 edges. The third case is that the subgraph includes 2 but not 1; it is symmetric to the second case. The fourth case is that the subgraph includes both 1 and 2, in which case it has at most 1 edge between 1 and 2, n' - 2 edges from 1 to other vertices, and n' - 2 edges from 2 to other vertices, for a total of at most 2n' - 3 edges.

For p-interesting graphs, the observation is that, by adding p new edges to a 0-interesting graph, the number of edges in the new graph is 2n + p, as required. The number of edges in each n'-vertex subgraph is the number of old edges plus the number of new edges. The number of old edges is at most 2n', as before. The number of new edges is at most p.