What is Bipartite Graph?

A bipartite graph (also referred to as a bigraph), is a graph whose vertices can be segregated into two disjoint sets such that no two vertices in the same set have an edge between them. They are equivalent to two-colorable graphs (a graph that can be colored with two colors such that no two adjacent vertices are of the same color).

Takeaways

Bipartite graphs have many applications. They are often used to represent binary relations between two types of objects.

What is a Bipartite Graph?

A bipartite graph has vertices which can be divided into two independent sets (say $P$ and $Q$) such that every edge $u\rightarrow v$ connects a vertex from the set $P$ to a vertex in set $Q$ or vice-versa. In other words, set $P$ and $Q$ are disjoint sets $i.e.$ $P\cap U=\phi$. Due to this property, there must not exist any edge $u\rightarrow v$ such that $u$ and $v$ belong to the same set.

If a graph is bipartite then it is possible to color all of its vertices using two colors, such that no two adjacent vertices have the same color.

For example:

Characteristics of Bipartite Graph

The characteristics of a bipartite graph are as follows:

• Vertices in a bipartite graph can be divided into two disjoint sets.
• No edges exist between vertices within each set.
• Every edge in a bipartite graph connects vertices from different sets.
• Bipartite graphs cannot contain odd-length cycles.
• The maximum degree of a vertex is equal to the size of the smaller set.
• Bipartite graphs can be colored using two colors.

Bipartite Graph Example

It can be seen that the set of all the vertices on the left-hand side has no edge between them and the set of all the vertices on the right-hand side has no edge between them. Hence, this graph fulfills all the conditions of the Bipartite graph.

It can be seen that all the vertices of the graph are colored using two colors $i.e.$ red and green such that no two adjacent vertices are of the same color. Hence this qualifies for the bipartite graph.

Similarly, this graph can also be colored using two colors, hence this is also a bipartite graph.

Algorithm to Check if a Graph is Bipartite or Not?

It is possible to check whether a graph is bipartite or not either by using the DFS or the BFS. Here, we will see the BFS approach. Let’s say we have a graph $G=(V, E)$, where $V$ is the number of vertices, and $E$ is the number of edges. The idea is to make an array (say color) of character type, which will be used to store the color assigned to $i^{th}$ vertex, and then start traversing the graph starting from any of the vertex in the range $[0, V-1]$.

The algorithm is as follows –

• Define the character array color, and initialize all its values by U. Here U denotes that the vertices are uncolored.
• Now define a Queue (say q) which is used to perform a breadth first search traversal.
• Push vertex 0 in the q, and assign a color to it (say R). Here, R denotes red color.
• Now, iterate while the q is not empty and do the following –
  • Deque the vertex from q and store the value in an integer (say u).
  • Iterate for all the adjacent vertices (say v) of u and to the following –
    • If v has already been colored with color[u], it means the graph can’t be colored with two colors and hence it is not bipartite.
    • Otherwise assign the complementary color of the color[u] to v $i.e.$ If u is colored with Red, assign the green color to v or vice-versa.
• If we have not encountered any two vertices colored with the same color it means the graph is bipartite.

Dry Run

Let’s dry run this approach on the given graph –

• As the first step, we will create an array (say color) of size $V$ which is 4, and assign U to all of them to denote that all of them are uncolored.
  Note that we will be following 1-based indexing for this whole dry run.
  So, we have color[] = {U, U, U, U}
• Now we will define q and push the first vertex (here 1) in the q and color it with Red color.
  Therefore after this step, we will have
  • color[] = {R, U, U, U}
  • q = [1]
• Now as per the algorithm we will iterate till q is not empty and do the following –
  • Iteration 1 –
    • Dequeue vertex from q and store in u $i.e.$ u=1
    • Iterate for all the uncolored adjacents of u, push them in the queue and color them with green color (since u is colored red).
      After this iteration, we will have
    • color[] = {R, G, U, G}
    • q = [2, 4]
  • Iteration 2 –
    • Dequeue vertex from q and store in u $i.e.$ u=2
    • Iterate for all the uncolored adjacents of u, push them in the queue and color them with red color (since u is colored green).
      After this iteration, we will have
    • color[] = {R, G, R, G}
    • q = [4]
  • Iteration 3 –
    • Dequeue vertex from q and store in u $i.e.$ u=3
    • Iterate for all the uncolored adjacents of u, push them in the queue and color them with red color (since u is colored green). But as it can be noticed, now there are no uncolored adjacent vertices of 3.
      After this iteration, we will have
    • color[] = {R, G, R, G}
    • q = []
  • The Queue is empty now, and we have not seen any violation of the bipartite graph property therefore we can conclude that the graph is a bipartite graph.

Java Implementation

import java.util.*;
public class Main{

    // Adjacency list
    static List<List<Integer>> adj;

    // Function to add edges. 
    static void addEdge(int u, int v){
        // Adding edge from u ---> v
        adj.get(u).add(v);

        // Adding edge from v ---> u
        adj.get(v).add(u);
    }

    static boolean checkBipartiteGraph(int V, int E){
        // Defining color array of character
        // type to store which color is assigned
        // to the ith vertex.
        // Here meaning of following letters 
        // are written against them
        // 1. U - Uncolored
        // 2. R - Colored red. 
        // 3. G - Colored green.
        char color[] = new char[V];

        // Initially uncoloring all the vertices.
        for (int i = 0; i < V; i++)
            color[i] = 'U';

        // Defining Queue to perform BFS on the graph.
        Queue<Integer> q = new LinkedList<>();

        // Pushing vetex 0 in node as the starting
        // vertex.
        q.add(0);

        // Coloring Vertex 0 with red color.
        color[0] = 'R';

        // Iterating while the queue is not empty.
        while (!q.isEmpty()){

            // Dequeue vertex from q.
            int u = q.poll();
            char c = color[u];

            // Iterate for all the adjacents of u.
            for(int v : adj.get(u)){
                // Checking if the adjacent is 
                // colored with color 'c'.
                if(color[v] == c) return false;

                // If 'v' is uncolored, coloring it with
                // complementary color of 'c'.
                if(color[v] == 'U'){
                    if(c == 'R')
                        color[v] = 'G';
                    else 
                        color[v]  = 'R';

                    // Adding 'v' in the queue.
                    q.add(v);                         
                }
            }
        }
        return true;

    }
    // Main function
    public static void main(String args[]){
        // Defining number of vertices
        int V = 4, E = 5;
        adj = new ArrayList<>();
        for(int i = 0; i < V; i++)
            adj.add(new ArrayList<>());

        /* Making the following graph
            0 ------- 1
            | \       |
            |   \     | 
            |     \   |
            |       \ |
            2 ------- 3      
        */
        addEdge(0, 1);
        addEdge(0, 2);
        addEdge(0, 3);
        addEdge(1, 3);
        addEdge(2, 3);

        // Checking if the graph is bipartite.
        if(checkBipartiteGraph(V, E))
            System.out.println("Graph 1 is Bipartite");
        else 
            System.out.println("Graph 1 is not Bipartite.");

        V = 4;
        E = 5;
        adj = new ArrayList<>();
        for(int i = 0; i < V; i++)
            adj.add(new ArrayList<>());

        /* Making the following graph
            0 ------- 1
            |         |
            |         | 
            |         |
            |         |
            2 ------- 3      
        */
        addEdge(0, 1);
        addEdge(0, 2);
        addEdge(1, 3);
        addEdge(2, 3);

        // Checking if the graph is bipartite.
        if(checkBipartiteGraph(V, E))
            System.out.println("Graph 2 is Bipartite");
        else 
            System.out.println("Graph 2 is not Bipartite.");
    }
}

Output –

Graph 1 is not Bipartite.
Graph 2 is Bipartite

C++ Implementation

#include<bits/stdc++.h>
using namespace std;

// Adjacency list
vector<vector<int>> adj;

// Function to add edges. 
void addEdge(int u, int v){
    // Adding edge from u ---> v
    adj[u].push_back(v);

    // Adding edge from v ---> u
    adj[v].push_back(u);
}

bool checkBipartiteGraph(int V, int E){
    // Defining color array of character
    // type to store which color is assigned
    // to the ith vertex.
    // Here meaning of following letters 
    // are written against them
    // 1. U - Uncolored
    // 2. R - Colored red. 
    // 3. G - Colored green.
    char color[V];

    // Initially uncoloring all the vertices.
    for (int i = 0; i < V; i++)
        color[i] = 'U';
    
    // Defining Queue to perform BFS on the graph.
    queue<int> q;

    // Pushing vetex 0 in node as the starting
    // vertex.
    q.push(0);
    
    // Coloring Vertex 0 with red color.
    color[0] = 'R';

    // Iterating while the queue is not empty.
    while (!q.empty()){

        // Dequeue vertex from q.
        int u = q.front();
        q.pop();
        char c = color[u];

        // Iterate for all the adjacents of u.
        for(int v : adj[u]){
            // Checking if the adjacent is 
            // colored with color 'c'.
            if(color[v] == c) return false;

            // If 'v' is uncolored, coloring it with
            // complementary color of 'c'.
            if(color[v] == 'U'){
                if(c == 'R')
                    color[v] = 'G';
                else 
                    color[v]  = 'R';

                // Adding 'v' in the queue.
                q.push(v);                         
            }
        }
    }
    return true;
}
// Main function
int main(){
    // Defining number of vertices
    int V = 4, E = 5;
    adj.resize(V);
    
    /* Making the following graph
        0 ------- 1
        | \       |
        |   \     | 
        |     \   |
        |       \ |
        2 ------- 3      
    */
    addEdge(0, 1);
    addEdge(0, 2);
    addEdge(0, 3);
    addEdge(1, 3);
    addEdge(2, 3);

    // Checking if the graph is bipartite.
    if(checkBipartiteGraph(V, E))
        cout << "Graph 1 is Bipartite\n";
    else 
        cout << "Graph 1 is not Bipartite.\n";


    // Redefining the graph.
    V = 4;
    E = 5;
    adj.erase(adj.begin(), adj.end());
    adj.resize(V);
    /* Making the following graph
        0 ------- 1
        |         |
        |         | 
        |         |
        |         |
        2 ------- 3      
    */
    addEdge(0, 1);
    addEdge(0, 2);
    addEdge(1, 3);
    addEdge(2, 3);

    // Checking if the graph is bipartite.
    if(checkBipartiteGraph(V, E))
        cout << "Graph 2 is Bipartite\n";
    else 
        cout << "Graph 2 is not Bipartite.\n";
}

Output –

Graph 1 is not Bipartite.
Graph 2 is Bipartite

Python Implementation

# Adjacency list
adj= []

# Function to add edges. 
def addEdge(u, v):
    # Adding edge from u ---> v
    adj[u].append(v)

    # Adding edge from v ---> u
    adj[v].append(u)


def checkBipartiteGraph(V, E):
    # Defining color array of character
    # type to store which color is assigned
    # to the ith vertex.
    # Here meaning of following letters 
    # are written against them
    # 1. U - Uncolored
    # 2. R - Colored red. 
    # 3. G - Colored green.
    color = ['U']*V

    # Initially uncoloring all the vertices.
    # for (int i = 0 i < V i++)
    #     color[i] = 'U'
    
    # Defining Queue to perform BFS on the graph.
    q = []

    # Pushing vetex 0 in node as the starting
    # vertex.
    q.append(0)
    
    # Coloring Vertex 0 with red color.
    color[0] = 'R'

    # Iterating while the queue is not empty.
    while (q):

        # Dequeue vertex from q.
        u = q.pop(0)
        c = color[u]

        # Iterate for all the adjacents of u.
        for v in adj[u]:
            # Checking if the adjacent is 
            # colored with color 'c'.
            if(color[v] == c):
                return False

            # If 'v' is uncolored, coloring it with
            # complementary color of 'c'.
            if(color[v] == 'U'):
                if(c == 'R'):
                    color[v] = 'G'
                else:
                    color[v]  = 'R'

                # Adding 'v' in the queue.
                q.append(v)                         
            
        
    
    return True

# Driver Code

# Defining number of vertices
V, E = 4, 5
adj = [[] for i in range(V)]

''' Making the following graph
    0 ------- 1
    | \       |
    |   \     | 
    |     \   |
    |       \ |
    2 ------- 3      
'''
addEdge(0, 1)
addEdge(0, 2)
addEdge(0, 3)
addEdge(1, 3)
addEdge(2, 3)

# Checking if the graph is bipartite.
if(checkBipartiteGraph(V, E)):
    print("Graph 1 is Bipartite")
else:
    print("Graph 1 is not Bipartite")

# Redefining the graph.
V = 4
E = 5
adj = [[] for i in range(V)]
''' Making the following graph
    0 ------- 1
    |         |
    |         | 
    |         |
    |         |
    2 ------- 3      
'''
addEdge(0, 1)
addEdge(0, 2)
addEdge(1, 3)
addEdge(2, 3)

# Checking if the graph is bipartite.
if(checkBipartiteGraph(V, E)):
    print("Graph 2 is Bipartite")
else:
    print("Graph 2 is not Bipartite")

Output –

Graph 1 is not Bipartite.
Graph 2 is Bipartite

Complexity Analysis

• Time Complexity – Since we are performing a BFS traversal, we visit each vertex once. Hence, the time complexity is O(V+E) if the graph is represented using an adjacency list, and O(V*V) if the graph is represented using an adjacency matrix.
• Space Complexity – No matter how the graph is represented, the space complexity is the same as that of the BFS algorithm i.e. O(V), which is due to the auxiliary array of size V.

Applications of Bipartite Graph

Bipartite graphs find diverse applications across various domains, including:

1. Matching Problems: Bipartite graphs offer an effective modeling tool for addressing matching problems, such as pairing job seekers with job vacancies or assigning students to project supervisors.
2. Social Networks: Bipartite graphs can represent user interactions, with one set of nodes denoting users and the other set representing interests, groups, or communities.
3. Web Search Engine: The query and click-through data of a web search engine can be aptly characterized using a bipartite graph, where one set of vertices represents queries and the other set corresponds to web pages.

Practice Problems

Problem 1 –

Question – Let’s say you have n vertices and you want to construct a bipartite graph from them, what is the maximum number of edges you can have in the graph.

Answer – $\lfloor{\frac{n^2}{4}}\rfloor$

Explanation –

The optimal way to achieve the most number of edges is to keep $\frac{n}{2}$ edges in the left set (say $P$) and remaining in the right set (say $Q$).

For example –

1. $n=5$
$|P| = \frac{5}{2}=2$
$|Q| = 5 – |P| = 3$
Now for each vertex in $P$ we can have $|Q|$ edges. Therefore edges are $2*3 = 6$ which is equal to $\lfloor{\frac{5^2}{4}}\rfloor$.

2. $n=6$
$|P| = \frac{6}{2}=3$
$|Q| = 6 – |P| = 3$
Now for each vertex in $P$ we can have $|Q|$ edges. Therefore edges are $3*3 = 9$ which is equal to $\lfloor{\frac{6^2}{4}}\rfloor$.

Problem 2 –

Question – Check if the graph given in the image below is bipartite or not and if it is partite find the vertices present in two different sets.

Answer – YES it is bipartite, Vertices in set $P = {v_1, v_3, v_6, v_8}$ and in the set $Q = {v_2, v_4, v_5, v_7}$

Explanation –
The graph can be colored in the following manner, and as you can see the vertices which are green in color are in set $P$, while those colored red are in set $Q$.

Conclusion

• Bipartite graphs can be colored using two colors, such that no two adjacent vertices share the same color.
• If the graph contains a cycle of odd length it means the graph is not a bipartite graph.
• Either DFS or BFS can be used to simulate the process of coloring to check whether the graph is bipartite or not.