3 votes 3 votes For which values of n are these graphs bipartite ? 1. $K_n$ 2. $C_n$ 3. $W_n$ 4. $Q_n$ Graph Theory discrete-mathematics kenneth-rosen graph-theory graph-connectivity + – dd asked Nov 22, 2016 recategorized Mar 6, 2019 by Pooja Khatri dd 5.3k views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments chaser commented Jul 9, 2017 reply Follow Share why n cannot be 2 in case of Qn? 0 votes 0 votes Jeevesh commented Jul 12, 2018 reply Follow Share For Qn : Qn is bipartite for any n. Let V1 consist of all vertices whose sum of coordinates is odd and let V2 consist of all vertices whose sum of coordinates is even. Two vertices in Qn are connected if and only if their coordinates differ in only one position, therefore the sums of their coordinates have different parity, so they are in different sets. 0 votes 0 votes Prateek Raghuvanshi commented Jan 13, 2019 reply Follow Share We know that for graph being bipartite it should be two colorable when n>=2.lets check one by one (1) $k_n$ is two colorable if and only if n=2 ,and we know that null graph with only one vertex also bipartite graph . (2)$C_n$ cycle graph is two colorable when it no. Of vertices are even so n=even graph will bipartite. (3) $w_n$ wheel graph can't be two colorable.so it can't be bipartite. (4)$Q_n$ hypercube graph is two colorable means it bipartite graph for all n. 2 votes 2 votes Please log in or register to add a comment.