Question

A bipartite graph is a graph $\mathbf{G}\mathbf{=}\mathbf{(}\mathbf{V}\mathbf{,}\mathbf{E}\mathbf{)}$whose vertices can be partitioned into two sets $\left(V=V1V2\mathrm{and}V1V2=\varphi \right)$ such that there are no edges between vertices in the same set (for instance, if , then there is no edge between and ).

(a) Give a linear-time algorithm to determine whether an undirected graph is bipartite.

(b) There are many other ways to formulate this property. For instance, an undirected graph is bipartite if and only if it can be colored with just two colors. Prove the following formulation:

an undirected graph is bipartite if and only if it contains no cycles of odd length.

(c) At most how many colors are needed to color in an undirected graph with exactly one odd length?

Short answer

(a) A linear-time algorithm to determine whether an undirected graph is bipartite is proved.

(b) An undirected graph is bipartite if and only if it is colored with just two colors. An undirected graph is bipartite if and only if it contains no cycles of odd length is proved.

(c) At most three colors are needed to color in an undirected graph with exactly one odd length.

Step-by-step solution

Explain Bipartite graph.

Bipartite graph is a graph G whose vertices are and v where all nodes of graphis connected itself or is not connected with any other node in a same graph as well as with graph . The vertices of$\mathit{u}$ are connected by vertices of vbut the nodes of these graph are not connected with any node of its own graph is known as bipartite graph.

A bipartite graph is defined as a graph where each vertex of its own set are never connected with each other. It must be connected by to the vertices of the different set of the graph.

Define a linear time algorithm to determine whether an undirected graph is bipartite.

a)

Following is the linear time algorithm to check if an undirected graph is bipartite:

1). Consider graph G which contain two sets of graphs named as u and v .

2). Take red color node as a source vertex and put this vertex in a set u . Then, color all the vertices blue which are directly connected to the source vertex and put these vertices to another set named v .

3). The blue vertex is connected with other node, color it red and put into the set of u graph.

4). The vertices of blue color and the vertices are in red color are not directly connected to each other. It means take all vertices of graph u is in the Red color and all vertices of graph v is in blue color.

5). Like that, assign red and blue color to all vertices and it satisfies all the constraints of m way coloring problem in which m = 2 .

Fig 1: Bipartite graph

Prove (b)

(b)

An undirected graph is bipartite if and only if it contains no cycles of odd length or if it contains cycle of even length then only it is bipartite graph. In the diagram shown in fig 2 , there are 0,1,2,3,4,5,6 some edges they are $0,1,2,3,4,5,6$. If 0 is the source vertex so color it red from 0 the two nodes are connected they are one and three color these both vertex with blue color. Now, look at the vertex 1 and 3 if any edge is connected to 1 and 3 then color it red.

From 1 again two edges are connected: they are 4 and 5 .So color these by blue color and again search the next node is 2 . Check whether it is connected to any red colored node or not, if no then color it red. Apply this method for each vertex and now the remaining vertex is 6 , which is connected by both 4 and 5 . Both 4 and 5 are colored with blue. Then, color the vertex as red. Through this it shows that the undirected graph is bipartite.

Fig:2 Showing undirected bipartite graph.

Fig:3 Showing undirected bipartite graph.

Find the number of colors needed in odd length cycle.

c)

The number of colorsneeded to color in an undirected graph with exactly one odd length is three because if the number of vertices is odd then the number of colors required is three. If the number of vertices is even then the number of colors required is two.

Hence, if number of vertices are odd then the number of colors required is three.