What is Bipartite Graph with Example?

Last Updated on November 30, 2023 by Ankit Kochar

In the realm of graph theory, a Bipartite Graph stands out as a distinctive and fascinating concept. Bipartite graphs are characterized by their unique structure, where the vertices can be divided into two disjoint sets, and edges only connect vertices from different sets. This concept has wide-ranging applications in various fields, including social networks, scheduling problems, and matching theory. This discussion delves into the definition of a Bipartite Graph, its key properties, and provides a concrete example to illustrate its structure and significance.

What is Bipartite Graph?

A Bipartite Graph is a type of graph in which we can partition the whole graph into two Bipartite Sets such that edges connect vertices present in one set to vertices in another set. A bipartite Graph does not have any edge which connects the vertex of one set to the vertex present in the same set. This will be more clear with the following example.

Let us consider this simple Graph.

The above graph can be partitioned into two sets as.

Here note that each color node is connected to a different color node.

The Bipartite Graph is also known as Two Colorable Graphs i.e., no two consecutive nodes in a Bipartite Graph are colored the same.

Properties of Bipartite Graphs

The properties of Bipartite Graphs are given below in brief. Knowing these will assist you further in learning the topic well.

• The vertices present in one set are not connected to the vertex present in the same set.
• A Bipartite graph is a simple graph, which means that there are no self-loops or multiple edges between the same pair of vertices.
• It may or may not be connected.
• For a graph to be Bipartite, it should not contain any cycle of odd length.

Examples of Bipartite Graphs

Here are some examples to demonstrate the concept of Bipartite Graphs.

Example 1 of Bipartite Graph
Let’s consider a simple example of a bipartite graph with 4 vertices, as shown in the following figure:

In this graph, the vertices can be divided into two disjoint sets, {A, C} and {B, D}, such that every edge connects a vertex in one set to a vertex in the other set. Therefore, this graph is a bipartite graph.

Example 2 of Bipartite Graph
Let’s consider another example of a bipartite graph with 6 vertices, as shown in the following figure:

The above graph contains a cycle of length 6 and the vertices or nodes can be divided into two sets i.e., {A, C, E} and {B, D, F}, such that every edge connects a vertex in one set to a vertex in the other set. This graph confirms to all the conditions of a bipartite graph. Therefore, this graph is also a bipartite graph.

Example 3 of Bipartite Graph
Now, let’s consider a graph that is not a bipartite graph, as shown in the following figure.

In this graph, we cannot divide the vertices into two sets such that every edge connects a vertex in one set to a vertex in the other set. Therefore, this graph is not a bipartite graph.

Algorithm to Check if the Given Graph is a Bipartite Graph or Not

Here is an algorithm for checking whether the given graph is a Bipartite or not using the BFS approach.

• Step 1: Start by picking an arbitrary vertex as the starting point and mark it as visited and add it to a queue.
• Step 2: Assign a color to the starting vertex (let’s say color red).
• Step 3: While the queue is not empty, take the first vertex from the queue and look at its neighbors.
• Step 4: For each neighbor of the current vertex, check if it has already been visited or not.
• Step 5: If the neighbor has not been visited, mark it as visited, add it to the queue, and assign it the opposite color of its parent vertex. So, if the parent vertex is colored red, the neighbor will be colored blue, and vice versa.
• Step 6: If the neighbor has been visited and has the same color as its parent vertex, then the graph is not bipartite.
• Step 7: Repeat steps 3 to 6 until all vertices have been visited or until a non-bipartite condition is detected.
• Step 8: If all vertices have been visited without any non-bipartite condition, then the graph is bipartite.

Dry Run to Check if the Given Graph is a Bipartite Graph or Not

Let us consider the following graph to understand the concept of the Bipartite Graph with 6 vertices named A, B, C, D, E, and F.

Let us dry-run the algorithm specified above on this graph.

• Step 1: Let us choose a random vertex (Here we have chosen A), and mark it as red. The graph will look like this.

  

• Step 2: Next step is to find all the neighbors of the vertex A, which are B and D. Mark the neighbor nodes in Blue color (since the previous node was colored red) as shown in the below image.

  

• Step 3: Now select the neighbors of the current node (B and D). The selected neighbors are:
  C and E -> Neighbors of B
  F -> Neighbors of D

  Color the selected vertices red (opposite to the current nodes color, blue). The graph will look like this.

  

• Step 4: The algorithm will now search for the unvisited neighbors of the current nodes (C, E, and F). Since there are no unvisited neighbors, the Algorithm will stop and return True as the answer.

  The above graph is a bipartite graph, as we can see that no two consecutive nodes are colored with the same color.

Code Implementation for Bipartite Graph

Here is the Code for Checking for Bipartite Graph in C++, Java, and Python.

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

const int V = 6;

bool isBipartiteUtil(int G[][V], int src, int colorArr[]){
    colorArr[src] = 1;
    queue<int> q;
    q.push(src);

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        if (G[u][u] == 1) return false;

        for (int v = 0; v < V; ++v) {
            if (G[u][v] && colorArr[v] == -1) {
                colorArr[v] = 1 - colorArr[u];
                q.push(v);
            }

            else if (G[u][v] && colorArr[v] == colorArr[u])
                return false;
        }
    }

    return true;
}

bool isBipartite(int G[][V]){
    int colorArr[V];
    for (int i = 0; i < V; ++i)
        colorArr[i] = -1;

    for (int i = 0; i < V; i++)
        if (colorArr[i] == -1)
            if (isBipartiteUtil(G, i, colorArr) == false)
                return false;

    return true;
}

int main(){
    int G[][V] = { { 0, 1, 0, 1, 0, 0 },
                { 1, 0, 1, 0, 1, 0 },
                { 0, 1, 0, 1, 0, 0 },
                { 1, 0, 1, 0, 0, 1 },
                { 0, 1, 0, 0, 0, 0 },
                { 0, 0, 0, 1, 0, 0 }};

    isBipartite(G) ? cout << "Yes" : cout << "No";
    return 0;
}

import java.util.*;

class Bipartite {
    public static int V = 4;

    public static boolean isBipartiteUtil(int G[][], int src, int colorArr[]){
        colorArr[src] = 1;

        LinkedList<Integer> q = new LinkedList<Integer>();
        q.add(src);

        while (!q.isEmpty()) {
            int u = q.getFirst();
            q.pop();

            if (G[u][u] == 1) return false;

            for (int v = 0; v < V; ++v) {
                if (G[u][v] == 1 && colorArr[v] == -1) {
                    colorArr[v] = 1 - colorArr[u];
                    q.push(v);
                }

                else if (G[u][v] == 1 && colorArr[v] == colorArr[u])
                    return false;
            }
        }

        return true;
    }

    public static boolean isBipartite(int G[][]){
        int colorArr[] = new int[V];
        for (int i = 0; i < V; ++i)
            colorArr[i] = -1;

        for (int i = 0; i < V; i++)
            if (colorArr[i] == -1)
                if (isBipartiteUtil(G, i, colorArr)
                    == false)
                    return false;

        return true;
    }

    public static void main(String[] args){
        int G[][] ={ { 0, 1, 0, 1, 0, 0 },
                { 1, 0, 1, 0, 1, 0 },
                { 0, 1, 0, 1, 0, 0 },
                { 1, 0, 1, 0, 0, 1 },
                { 0, 1, 0, 0, 0, 0 },
                { 0, 0, 0, 1, 0, 0 }};

        if (isBipartite(G))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}

class Graph():
    def __init__(self, V):
        self.V = V
        self.graph = [[0 for column in range(V)]
                    for row in range(V)]

        self.colorArr = [-1 for i in range(self.V)]

    def isBipartiteUtil(self, src):
        queue = []
        queue.append(src)

        while queue:
            u = queue.pop()

            if self.graph[u][u] == 1:
                return False

            for v in range(self.V):
                if (self.graph[u][v] == 1 and self.colorArr[v] == -1):
                    self.colorArr[v] = 1 - self.colorArr[u]
                    queue.append(v)

                elif (self.graph[u][v] == 1 and self.colorArr[v] == self.colorArr[u]):
                    return False

        return True

    def isBipartite(self):
        self.colorArr = [-1 for i in range(self.V)]
        for i in range(self.V):
            if self.colorArr[i] == -1:
                if not self.isBipartiteUtil(i):
                    return False
        return True


g = Graph(6)
g.graph = [ [0, 1, 0, 1, 0, 0 ],
                [1, 0, 1, 0, 1, 0 ],
                [ 0, 1, 0, 1, 0, 0 ],
                [ 1, 0, 1, 0, 0, 1 ],
                [ 0, 1, 0, 0, 0, 0 ],
                [ 0, 0, 0, 1, 0, 0 ]]

print ("Yes" if g.isBipartite() else "No")

Output

Yes

Time Complexity of Bipartite Graph

The Time Complexity of the above code is O(V*V) because we are traversing the Adjacency Matrix. This can be reduced to O(V+E) by using the adjacency list for storing the graph.

Space Complexity of Bipartite Graph

The Space Complexity is O(V) since we are using an extra array for the color vector and also for the queue.

Applications of Bipartite Graph

Bipartite Graphs Are used in several fields. Some of the applications of Bipartite Graphs are given below.

• Bipartite Graphs are used to solve the Matching Problems. For example, it can be used for assigning employees a number of tasks or assigning students to different courses.
• Bipartite graphs can be used to make recommendation systems, where one set of vertices represents users and the other set represents items. If a user has rated an item, an edge is drawn between the corresponding vertices. The goal is to recommend items to users based on their preferences.
• Bipartite graphs, in which one set of vertices represents people and the other set represents groups, can be used to model social networks. If the user is a member of the group, an edge is drawn between them.

Conclusion
In conclusion, the Bipartite Graph introduces a captivating dimension to graph theory by dividing its vertices into two distinct sets and establishing connections exclusively between vertices from different sets. This elegant structure finds practical applications in diverse fields, showcasing its versatility. Understanding Bipartite Graphs is not only essential for theoretical aspects of graph theory but also holds practical value in solving real-world problems where relationships can be neatly categorized into two distinct groups.

Frequently Asked Questions(FAQs) related to Bipartite Graph with Example

Here are some Frequently Asked Questions on “What is Bipartite Graph”.

Q1: Can a bipartite graph have cycles of odd length?
A1: No, a bipartite graph cannot have cycles of odd length, as each edge connects a vertex in one set to a vertex in the other set, so a cycle must have an even number of edges.

Q2: How are Bipartite Graphs used in real-world scenarios?
A2: Bipartite Graphs find applications in various domains, such as social network analysis, scheduling problems, and matching theory. In social networks, for instance, they can model relationships between different types of entities, like users and events.

Q3: Can all graphs be classified as Bipartite?
A3: No, not all graphs are Bipartite. A graph is considered Bipartite only if its vertices can be divided into two disjoint sets, and edges only connect vertices from different sets. If a graph cannot be partitioned in this way, it is not Bipartite.

Q4: How is the bipartition of vertices in a Bipartite Graph determined?
A4: The bipartition of vertices in a Bipartite Graph is determined by arranging the vertices in two sets such that no edge connects vertices within the same set. Finding such a partition may involve graph algorithms or inspection of the graph’s structure.

Q5: Can you provide an example of a Bipartite Graph?
A5: Certainly, consider a graph modeling the relationships between students and the courses they are enrolled in. If the vertices represent students and courses, and edges connect students to the courses they are taking, this graph would be a Bipartite Graph, with students in one set and courses in another.