Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Sample Example
3.1.
Input
3.2.
Output
3.3.
Explanation
4.
Approach
5.
Algorithm
6.
Code
6.1.
C++ Code
6.2.
Java Code
6.3.
Python Code
6.4.
Time Complexity: O(n)
7.
Frequently Asked Questions
7.1.
How many colors are required to color a bipartite graph?
7.2.
Is it possible for a bipartite graph to have a cycle of odd length?
7.3.
What is the maximum number of edges that a bipartite graph can have?
8.
Conclusion
Last Updated: Mar 27, 2024

Maximum Number of Edges that can be added to a tree so that it stays a Bipartite graph

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

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.

Maximum Number of Edges that can be added to a tree so that it stays a Bipartite graph

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Sample Example

Input

{1,2}
{1,3}
{2,4}
{3,5}

Output

2

Explanation

explanation graph

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.

Bipartite Graph

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


Time Complexity: O(n)

Check out this problem - Duplicate Subtree In Binary Tree

Frequently Asked Questions

How many colors are required to color a bipartite graph?

Two colors are required to color a bipartite graph.

Is it possible for a bipartite graph to have a cycle of odd length?

No, a bipartite graph cannot have an odd length cycle.

What is the maximum number of edges that a bipartite graph can have?

A bipartite graph can have most: (node with color 0) * (node with color 1) number of edges.

Conclusion

In this article, we have extensively discussed the Maximum Number of Edges that can be added to a tree so that it remains a Bipartite graph problem.

After reading about this problem, are you not feeling excited to read/explore more articles on Graph? Don't worry; Coding Ninjas has you covered. To learn about the different types of graphs and applications, what is the difference between a graph and a tree, and what is breadth-first search.  

If you wish to enhance your skills in Data Structures and AlgorithmsCompetitive ProgrammingJavaScript, 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. 

Do upvote if you find the blogs helpful.

Happy Learning!

Thank you
Previous article
Find the Path in a Rectangle with Circles
Next article
Minimum number of moves needed to move from one cell of the matrix to another
Live masterclass