Graph Theory

Question

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

Comments

Do you really want to listen my language? what do you think "bullshit" means? Hoshiyar aadami.

---

@Tesla! Explain the question to me ? Hoshiyar.

Tesla! likh dene se tesla ho jayega.

---

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

Answer 1

N=2

Because 

A bipartite graph does not have odd cycle

and for  (n>2) all complete graph contain odd cycle

Answer 2

n∗(n−1)/2=⌈n²/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

Comments

Unable to understand your answer ..Please explain it more clearly.

---

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.

---

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?

---

Yes you are correct