# Check whether a given graph is Bipartite or not

### Check whether a given graph is Bipartite or not

A Bipartite Graph is a graph whose vertices can be divided into two independent sets, U and V such that every edge (u, v) either connects a vertex from U to V or a vertex from V to U.

In other words, for every edge (u, v), either u belongs to U and v to V, or u belongs to V and v to U. We can also say that there is no edge that connects vertices of same set.

Solution :

• It can be easily solve by vertex color algorithm where color is 2
• We alternatively color a vertex, it means
• If vertex color is red, its neighbours color would be yellow and neighbours’s neighbour color would be red again.
• During painting if we found that color of two adjacent vertices is same the graph is not Bipartite.

Note:

• It is possible to color a cycle graph with even cycle using two colors.
• It is not possible to color a cycle graph with odd cycle using two colors.

Latest Source Code:
Github: BipartiteGraphChecker.java

Output:

```0 -> [1, 3]
1 -> [0, 2]
2 -> [1, 3]
3 -> [0, 2]

Is Graph Bipartite: true

```
Author: