Acyclic Graph- Editorial

Problem Link:
Contest
Practice

Author: amankedia1994

Tester: legend-killer

Editorialist: sumeet_varma

Difficulty:

Easy - Medium

Pre-requisites: - Bipartite Graphs

Problem: Given an acyclic graph with N nodes and E undirected edges and degree of every node is < 3, find the maximum number of edges that can be added, such that there is no cycle of odd length in the final graph.

Quick Explanation: Answer is always n^2/4 - m.

Explanation:

We want that the final graph should not have any cycle of odd length.
β€œA graph is bipartite if and only if it does not contain an odd cycle”.
Thus we want out final graph to be bipartite.

If a bipartite graph is divided into two pieces, say of size p and q, where p + q = n. Then the maximum number of edges is p*q. Using calculus we can deduce that this product is maximal when p = q or |p – q| <= 1, in which case it is equal to p*q = n^2/4.

Thus our final graph has upper bound of number of edges as n^2/4. So our answer has upper bound of number of edges as n^2/4 – m.

Let’s see how we can always achieve this.

For an acyclic graph with degree of all vertices < 3, the only possible shape of each component is a linear chain of vertices with size >= 1 and size <= n.

To get maximal ans, we want that |p – q| <= 1 where p and q are sizes of bipartites.
We will prove that we can get maximum ans by induction.

Initially p = q = 0.

Suppose we are processing kth chain of vertices.
Let x be number of vertices in kth chain.

Case 1: x is even.

If x is even, we can add x/2 vertices (all vertices at even positions in the chain) to p and x/2 vertices (all vertices at odd position in the chain) to q and there would be no change to |p – q|. We can do this because each edge in chain is between a vertex with even position and a vertex with odd position.

Case 2: x is odd.

In this case, we can add x/2 + 1 vertices to one part and x/2 vertices to other part. This changes |p – q| by 1. But still we can maintain |p – q| <= 1. Consider following three cases.

Case 2a: p = q.

We add x/2 + 1 to p and x/2 to q. So p – q = 1 and |p – q| <= 1

Case 2b: p – q = -1

We add x/2 + 1 to p and x/2 to q. So p – q = 0 and |p – q| <= 1

Case 2c: p – q = 1

We add x/2 to p and x/2 + 1 to q. So p – q = 0 and |p – q| <= 1

Thus after adding each chain in our bipartite we can maintain |p – q| <= 1. Also initially |p – q| = 0. Thus we can prove, after adding all chains in bipartite, |p – q| <= 1.
So we can create a complete bipartite graph with p * q = n^2 / 4 edges. So total maximum number of new edges we can add = n^2/4 – m.

Ofcourse all this is for proof. Code would be just to input n,m and print n^2/4 - m.

2 Likes

Cool question and a nice editorial :slight_smile: Kudos _/_

1 Like