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/4m.

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.

1 Like

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

1 Like
//