recategorized by
781 views
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
recategorized by

2 Answers

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

Related questions

0 votes
0 votes
0 answers
1
Sahil_Lather asked Jan 27, 2023
489 views
Let Gn be the complete bipartite graph K13, 17 then the chromatic number of G̅n is _____ (G̅n is complement of Gn and n = 30)A13B17Cn(n−1)2−13×17Dn(n−1)2−2
1 votes
1 votes
1 answer
3
Lone Wolf asked Sep 23, 2018
1,005 views
consider a complete bipartite graph K(3,3)The ratio of total number of possible vertex induced subgraphs to the total number of possible edge induced subgraph in given bi...
0 votes
0 votes
2 answers
4