Do you think IIT Guwahati certified course can help you in your career?
Introduction
In this article, we will discuss about the Maximum Number of Edges that can be added to a tree so that it remains a Bipartite graph problem, along with a sample test case and approach to solve the problem.
Problem Statement
Every tree is a Bipartite Graph as it can be broken down into two disjoint sets with alternate levels. In other words, it can be said that a tree can be colored with two colors such that every alternate level has the same color.
Given a tree where the tree edges are represented as vertex pairs, the task is to find the maximum number of edges that can be added to this tree so that it remains a Bipartite Graph.
Sample Example
Input
{1,2}
{1,3}
{2,4}
{3,5}
Output
2
Explanation
It is found that on coloring the graph: (1,4,5) and (2,3) form two different sets. As 1 is connected from 2 as well as 3, we are only left with edges 4 and 5. Now, since 4 already is connected to 2 and similarly 5 is connected to 3. The only remaining option is to connect (4,3) and (5,2).
Approach
A bipartite graph is defined as a graph whose vertices can be divided into two sets, U and V, such that every edge (u,v) connects either a vertex from U to V or vice-versa. In other words, a bipartite graph, when colored using two colors, yields two sets, such that all the vertices in a set are colored with the same color. A bipartite graph can have a maximum of countColor0 * countColor1 edges, where countColor0 represents the number of edges with the color:0 and countColor1 represents the number of edges with color:1. The values of countColor0 and countColor1 can be easily found by using a simple DFS or BFS traversal.
We know that a tree having n nodes can have n-1 edges.
So, the Maximum number of edges that can be added to a tree with n nodes so that it remains a Bipartite Graph is: (countColor0 * countColor1) - (n-1)
Algorithm
Color the graph/tree with two colors using either DFS Algorithm or BFS.
While coloring, keep track of the counts of nodes colored with the two colors in variables named countColor0 and countColor1.
Calculate the maximum number of edges a bipartite graph can have using the formula: countColor0 * countColor1
Now, calculate the result using formula: (countColor0 * countColor1) - (n-1)
Code
C++ Code
#include <bits/stdc++.h>
using namespace std;
// dfs traversal function
void countColorNodes(vector<int> adj[], int u, int parentNode, bool color, int *countColor)
{
// Increment the count of nodes with the current color
countColor[color]+=1;
// use the adjacency list to visit the neighbors
for (int v = 0; v < adj[u].size(); v++) {
// keep track of the parent node.
// do not recur for the parent node
if (adj[u][v] != parentNode)
// invert the color when calling for the next level
countColorNodes(adj, adj[u][v], parentNode, !color, countColor);
}
}
// function that counts how many nodes are of color0 & color1
int countColorNodesutill(vector<int> adj[])
{
// stores the counts of nodes with two colors
// countColor[0]: stores the count of nodes with color:0
// countColor[1]: stores the count of nodes with color:1
int countColor[2]={0};
// A dfs traversal is used to find the number of nodes of each color
countColorNodes(adj, 1, 0, 0, countColor);
return (countColor[0] * countColor[1]);
}
int maxEdges(vector<int> adj[], int n){
// variable to store maximum no. of edges in a bipartite graph
int maxEdgesBipartite = countColorNodesutill(adj);
int result = maxEdgesBipartite - (n-1);
return result;
}
int main()
{
int V = 5;
vector<int> adj[V + 1];
adj[1].push_back(2);
adj[1].push_back(3);
adj[2].push_back(4);
adj[3].push_back(5);
cout <<"The maximum edges that can be added to the tree: "<<maxEdges(adj, V);
return 0;
}
Output
The maximum edges that can be added to the tree: 2
Java Code
import java.util.*;
class MaxEdges
{
// stores the counts of nodes with two colors
// countColor0: stores the count of nodes with color:0
// countColor1: stores the count of nodes with color:1
static int countColor0=0, countColor1=0;
// dfs traversal function
static void countColorNodes(Vector<Integer> adj[], int u,
int parentNode, boolean color)
{
// Increment the count of nodes with the current color
if(!color)
countColor0+=1;
else
countColor1+=1;
// use the adjacency list to visit the neighbors
for (int v = 0; v < adj[u].size(); v++)
{
// invert the color, when calling for the next level
if (adj[u].get(v) != parentNode)
countColorNodes(adj, adj[u].get(v), u, !color);
}
}
// function that counts how many nodes are of color0 & color1
static int countColorNodesutill(Vector<Integer> adj[])
{
// A dfs traversal is used to find the number of nodes of each color
countColorNodes(adj, 1, 0, false);
return (int) (countColor0 * countColor1);
}
// A function to calculate the maximum number of edges that can be added to a graph so that it remains Bipartite.
static int maxEdges(Vector<Integer> adj[], int n)
{
// variable to store maximum no. of edges in a bipartite graph
int maxEdgesBipartite = countColorNodesutill(adj);
int result = maxEdgesBipartite - (n-1);
return result;
}
public static void main(String[] args)
{
int V = 5;
Vector<Integer>[] adj = new Vector[V + 1];
for (int x = 0; x < V + 1;x++)
adj[x] = new Vector<Integer>();
adj[1].add(2);
adj[1].add(3);
adj[2].add(4);
adj[3].add(5);
System.out.println("The maximum edges that can be added to the tree: " + maxEdges(adj, V));
}
}
Output:
The maximum edges that can be added to the tree: 2
Python Code
#dfs traversal function
def countColorNodes(adj, u, parentNode, color):
#Increment the count of nodes with the current color
countColor[color] += 1
# use the adjacency list to visit the neighbors
for v in range(len(adj[u])):
# invert the color when calling for the next level
if (adj[u][v] != parentNode):
countColorNodes(adj, adj[u][v],
u, not color)
#function that counts how many nodes are of color0 & color1
def countColorNodesutill(adj):
#A dfs traversal is used to find the number of nodes of each color
countColorNodes(adj, 1, 0, 0)
return (countColor[0] *
countColor[1])
# a function that returns the no. of edges that can be added
def maxEdges(adj, n):
#variable to store maximum no. of edges in a bipartite graph
maxEdgesBipartite = countColorNodesutill(adj)
result = maxEdgesBipartite - (n-1)
return result
#stores the counts of nodes with two colors
#countColor[0]: stores the count of nodes with color:0
#countColor[1]: stores the count of nodes with color:1
countColor = [0, 0]
n = 5
adj = [[] for c in range(n + 1)]
adj[1].append(2)
adj[1].append(3)
adj[2].append(4)
adj[3].append(5)
print("The maximum edges that can be added to the tree: ", maxEdges(adj, n))
Output:
The maximum edges that can be added to the tree: 2
If you wish to enhance your skills in Data Structures and Algorithms, Competitive Programming, JavaScript, etc., you should check out our Guided path column at Code studio. We at Coding Ninjas Studio organize many contests in which you can participate. You can also prepare for the contests and test your coding skills by giving the mock test series available. In case you have just started the learning process, and your dream is to crack major tech giants like Amazon, Microsoft, etc., then you should check out the most frequently asked problems and the interview experiences of your seniors that will surely help you in landing a job in your dream company.
19+ registered 
