0 votes 0 votes What is largest number of maximal independent set of complete bipartite graph K(4,2)? a)2 b)3 c)4 d)6 Graph Theory bipartite-graph graph-theory + – neha singh asked Oct 11, 2016 • edited Oct 10, 2023 by Hira Thakur neha singh 3.3k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply dd commented Oct 11, 2016 reply Follow Share 4 is the answer 1 votes 1 votes neha singh commented Oct 11, 2016 reply Follow Share it is given 6 on book 0 votes 0 votes Habibkhan commented Oct 11, 2016 reply Follow Share Answer should be 4 only.See we know that for bipartite complete graph Km,n , we can partition the vertex set into 2 sets such that one contains m and other contains n elements(vertices) and within each of this sets there does not exist any edge between any pair of vertices.So it is nothing but independent set. So for bipartite complete graph Km,n , we have 2 independent sets.So here max(4,2) = 4.Hence 4 should be the size of largest maximal independent set. 2 votes 2 votes Please log in or register to add a comment.
1 votes 1 votes answer should be 4 only which is max(v1,v2) where v1 and v2 are the set of vertices cse23 answered Oct 14, 2016 cse23 comment Share Follow See all 0 reply Please log in or register to add a comment.
