**A bipartite graph** is a type of graph in which we divide the vertices of a graph into two sets. There are no edges between the vertices of the same set. Here in the bipartite_graph, the length of the cycles is always even. Basically, the sets of vertices in which we divide the vertices of a graph are called the part of a graph. Let’s see the example of Bipartite Graph.

Here we can divide the nodes into 2 sets which follow the bipartite_graph property. Let say set containing 1,2,3,4 vertices is set X and set containing 5,6,7,8 vertices is set Y. We see clearly there are no edges between the vertices of the same set.

**Note: Complete Bipartite graph** is a special type of bipartite_graph in which every vertex of set X is connected to every vertex of set Y through an edge.

Table of Contents

## Properties of Bipartite Graph

- It does not contain odd-length cycles.
- It must be two colors.
- Subgraphs of a given bipartite_graph are also a bipartite_graph.
- Here, the Sum of the degree of vertices of set X is equal to the sum of vertices of set Y.
- If we need to check the spectrum of the graph is symmetric then we check the graph is bipartite or not. If it is not a bipartite_graph then we can say that the spectrum of the graph is not symmetric.
- A bipartite_graph consisting of N vertices can have at most
**(1/4)*N*N edges**.

There are basically two ways to check the graph is bipartite or not:

- Using
**BFS**to check that graph is containing the**odd-length cycle**or not. If cycle with odd length found then we say its not a BG. - Using
**DFS**to check the graph is**2 colorable**or not. If it is two colorable then we say that graph is bipartite in nature.

## Check Graph is Bipartite or not using BFS

### Algorithm

Step:1 Make a graph using the adjacency list. Step:2 For i in range 1 to N: a) If i is unvisited then: i) BFS(i). ii) If we found the odd-length cycle then we stop the process and print graph is not bipartite.

## Check Graph is Bipartite or not using DFS

### Algorithm

Step:1 Use color 0,1 to color the vertices. Step:2 Call DFS(start). Step:3 Assign the opposite color of the parent to the current node and call DFS to visit the neighbors of current node. Step:4 If any step we find the color of two nodes connected by each other is same then we return false. Step:5 If we visit all the nodes and don't find the color of two nodes connected by each other is same then we return true.

## Implementation

/*C++ Implementation for check a graph is bipartite or not.*/ #include<bits/stdc++.h> using namespace std; /*function to check for graph is bipartite or not.*/ int check_biaprtite(int node,vector<int> v[],bool visited[],int assign[]) { /*visited all connected nodes to node*/ for(int itr: v[node]) { /*if connected node is unvisited then check_biaprtite*/ if(!visited[itr]) { visited[itr]=true; assign[itr]=!assign[node]; if(!check_biaprtite(itr,v,visited,assign)) { return 0; } } /*if two adjacent node have the same color then return false*/ else if(assign[itr]==assign[node]) { return 0; } } /*else return true*/ return 1; } int main() { int nodes,edges; /*take inputs the value of node and edges*/ cin>>nodes>>edges; vector<int> v[nodes+1]; /*create undirected graph*/ for(int i=0;i<edges;i++) { int x,y; cin>>x>>y; /*add edge between x -> y*/ v[x].push_back(y); /*add edge between y -> x*/ v[y].push_back(x); } bool visited[nodes+1]; /*set all the nodes as unvisited*/ memset(visited,false,sizeof(visited)); int assign[nodes]; int test; /*check for all the nodes in the graph*/ for(int i=1;i<=nodes;i++) { /*if node is unvisited*/ if(!visited[i]) { visited[i]=true; assign[i]=0; /*check for this connected component*/ test=check_biaprtite(i,v,visited,assign); /*if test is 1 then graph is not Bipartite*/ if(test==1) { goto label; } } } label:; /*print the result*/ if(test==1) { cout<<"Graph is Bipartite"<<endl; } else { cout<<"Graph is not Bipartite"<<endl; } return 0; }

8 6 1 6 6 3 3 8 5 2 2 7 7 4

Graph is Bipartite

## Time Complexity

**O(N+E)** where N is the number of nodes and E is the number of edges. During creating graph we use O(N+E) time which is the maximum possible for the whole process.

## Space Complexity

**O(N+E)** where N is the number of nodes and E is the number of edges. Creating the adjacency list we use maximum space which is O(N+E).