UGC NET CSE | December 2015 | Part 2 | Question: 4

Question

Consider the graph given below:

The two distinct set of vertices, which make the graph bipartite are

• A. $(v_1, v_4, v_6); (v_2, v_3, v_5, v_7, v_8)$
• B. $(v_1, v_7, v_8); (v_2, v_3, v_5, v_6)$
• C. $(v_1, v_4, v_6, v_7); (v_2, v_3, v_5, v_8)$
• D. $(v_1, v_4, v_6, v_7, v_8); (v_2, v_3, v_5)$

Answer 1

C is answer.

(v₁,v₄,v_6,v₇ ) put these vertex with red color

(v₂,v₃,v₅,,v₈) put these vertex with blue color

it can be seen in set Between any two vertex there is direct no edge.

Answer 2

C option answer 

Answer 3

as we know a graph is bipartite if it can be divided into 2 set of vertices such that each edge in graph joins vertex of one part to vertex of another

let v1v2=a ,v1v3=b , v1v5=c ,v2v4=d ,v2v6=e ,v3v4=f, v3v7=g, v4v8=h ,v5v6=i ,v5v7=j , v6v8=k

option C  is the ans since 

edge a ,b,c,d, e, f, g, h, i, j, k will join vertex of left hand side to r.h.s

v1,v4,v6,v7                         v2 , v3, v5, v8