Which of the following are bipartite If you say a graph is n

Which of the following are bipartite? If you say a graph is not bipartite, exhibit an odd cycle in the graph. If you say it is, list the two sets in an appropriate partition of the vertices.

Solution

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.

first graph is bipartite

let us see the two sets U and V

second graph is bipartite

Let us see the two sets U and V

third graph is bipartite

Let us see the two sets U and V

U	V
a	e
b	f
c	g
d	h
i	j
	k
	l