0 votes 0 votes let G=(V,E) be an connected graph, let $\left | V \right |= n$ Find largest value of n such that i) G is complete & ii) G is bipartite with valid proof Graph Theory graph-theory bipartite-graph + – Tesla! asked Apr 2, 2017 recategorized Jul 6, 2022 by Lakshman Bhaiya Tesla! 781 views answer comment Share Follow See all 8 Comments See all 8 8 Comments reply rude commented Apr 2, 2017 reply Follow Share Dear @Tesla! your question is incomplete. 0 votes 0 votes Srinivas Rao commented Apr 2, 2017 reply Follow Share Sir @rude why can't n be equal to 2 can you tell why the question in your opinion is incomplete 0 votes 0 votes Vijay Thakur commented Apr 2, 2017 reply Follow Share yes question is incomplete! 0 votes 0 votes rude commented Apr 3, 2017 reply Follow Share Dear @srinivas rao.. because it does not make any sense. it's a bullshit. –2 votes –2 votes Tesla! commented Apr 4, 2017 reply Follow Share @rude mind your language 0 votes 0 votes rude commented Apr 5, 2017 reply Follow Share Do you really want to listen my language? what do you think "bullshit" means? Hoshiyar aadami. –1 votes –1 votes rude commented Apr 5, 2017 reply Follow Share @Tesla! Explain the question to me ? Hoshiyar. Tesla! likh dene se tesla ho jayega. 0 votes 0 votes Tesla! commented Apr 5, 2017 reply Follow Share let x1 be graph which is complete let x2 be a graph which is bipartite under what condition x1=x2 (in terms of edges and vertices) by solving equation below it comes out to be that 2 vertex one edge simple graph is the only graph which is complete as well as bipartite, there exist no other solution to this problem 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes N=2 Because A bipartite graph does not have odd cycle and for (n>2) all complete graph contain odd cycle Shubham Pandey 2 answered Apr 3, 2017 Shubham Pandey 2 comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes n∗(n−1)/2=⌈n2/4⌉ 1st one is condition maximum edge in complete graph a second is condition for maximum edges in bipartite graph $\left \lceil \frac{2n^{2}-2n-n^{2}}{4} \right \rceil$ $n^{2}-2n=0$ solving it we get n=0 or n=2 n=0 is not possible so n=2 is only possible Tesla! answered Apr 3, 2017 Tesla! comment Share Follow See all 4 Comments See all 4 4 Comments reply Shubham Sharma 2 commented Apr 5, 2017 reply Follow Share Unable to understand your answer ..Please explain it more clearly. 0 votes 0 votes Tesla! commented Apr 5, 2017 reply Follow Share two condition that graph should be complete and graph should be bipartite if graph is complete then it will have n(n-1)/2 edges and for an bipartite graph maximum number of edges is $\left \lceil \frac{n^{2}}{4}\right \rceil$ just equating we get 2 solution 0 and 2 0 is not possible because then it wont be graph hence 2 vertex 1 edge graph is the only graph which is complete and bipartite no other graph exist which satisfy this condition. 2 votes 2 votes Shubham Sharma 2 commented Apr 5, 2017 reply Follow Share The reason behind equating is that the question is asking for a common value of n for which graph is both complete and bipartite..am i correct? 0 votes 0 votes Tesla! commented Apr 5, 2017 reply Follow Share Yes you are correct 0 votes 0 votes Please log in or register to add a comment.