0 votes 0 votes Graph Theory graph-theory discrete-mathematics bipartite-graph + – Çșȇ ʛấẗẻ asked Aug 29, 2023 • recategorized Oct 9, 2023 by Hira Thakur Çșȇ ʛấẗẻ 283 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes Bipartite graph :- Informally, if there exist two non-empty independent sets such that no edge present within each set elements. In option A :- if you put K in one ste and j in another set then there is no place to put L anywhere. So we can not put make two independent set here therefore it is not bipartite graph. Option B :- correct Here two independent sets are A = { F G D C } B = { E B H I } so it is bipartite. Option C :- Wrong, it contains odd length cycle. Option D :- Here two independent sets are A = { M K P } B = { L N O } so it is bipartite. Mr coder answered Aug 30, 2023 • edited Sep 11, 2023 by Mr coder Mr coder comment Share Follow See all 2 Comments See all 2 2 Comments reply Harsh Saini_1 commented Sep 7, 2023 reply Follow Share Option C cannot be a Bi-partite graph since it contains an Odd cycle (LIH). Also , Option D is Bi-partite since it does not contain any Odd Cycle. 1 votes 1 votes Hira Thakur commented Oct 9, 2023 reply Follow Share Condition for checking whether a graph is bipartite or not: A bipartite graph is 2 colorable means its chromatic number is $2$. A bipartite graph does not contain any odd-length cycle. Here A and C have odd length cycles. so it is not a Bipartite graph. B and D have chromatic numbers =2 so it is a bipartite graph. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes option B and D are 2 colorable so they are the Bipartite graphs rohit vishwakarma answered Sep 11, 2023 rohit vishwakarma comment Share Follow See all 0 reply Please log in or register to add a comment.