3.2k views

How many graphs on $n$ labeled vertices exist which have at least $\frac{(n^2 - 3n)}{ 2}$ edges ?

1. $^{\left(\frac{n^2-n}{2}\right)}C_{\left(\frac{n^2-3n} {2}\right)}$
2. $^{{\large\sum\limits_{k=0}^{\left (\frac{n^2-3n}{2} \right )}}.\left(n^2-n\right)}C_k\\$
3. $^{\left(\frac{n^2-n}{2}\right)}C_n\\$
4. $^{{\large\sum\limits_{k=0}^n}.\left(\frac{n^2-n}{2}\right)}C_k$
retagged | 3.2k views

Let $a = \frac{n(n-1)}{2}, b = \frac{n^2 -3n}{2}$

Minimum no of edges has to be $\frac{n^2 -3n}{2} = b$.

Maximum no of edges in simple graph = $\frac{n(n-1)}{2} = a$.

So, no of graph with minimum $b$ edges :

$= C(a,b) + C(a,b+1) + C(a,b+2) + \dots +C(a,a)$

$= C(a,a-b) + C(a,a-(b+1)) + C(a,a-(b+2)) + \dots +C(a,0)$

$= C(a,n) + C(a,n-1) + C(a,n-2) + \dots +C(a,0))$$\;\left(\because a-b = n \right) = C\left(\frac{n(n-1)}{2},n\right) + C\left(\frac{n(n-1)}{2}, n-1\right) \\+ C\left(\frac{n(n-1)}{2},n-2\right) + \dots +C\left(\frac{n(n-1)}{2},0\right) =\sum\limits_{k=0}^{n} {}^{\left(\frac{n^2-n}{2}\right)}C_k Option (D).. answered by Veteran (55.6k points) edited by +2 @sachin mttal1 i got one thing best in ur answer . That is And it is not hard to proof. Bcz it is really hard to proof during exam. +7 lol, In exam this question is not meant to solve in this way. We should take small value of n and check options. 0 @ARJUN SIR #plz explain i am not understand solution which is selected best ?? 0 suppose we have n = 4 then max no of edges possible will be 6 here nw for atleast ( N^(2) - 3* N) / R put n = 4 here we will get 2 it means atleast 2 edges should be there there in graph which means 6C2 + 6C3 + 6C4 + 6C5 + 6C6 which would be equal to the value u get by expanding the d option with given example values 0 But option D) considers \binom{6}{0}+\binom{6}{1}+\binom{6}{2}+\binom{6}{3}+\binom{6}{4}+\binom{6}{5}+\binom{6}{6} that means it also considers \binom{6}{0}+\binom{6}{1} which should not be there as per question right? 0 maximum upper bound equals to n = 4 so u would stop your expansion up to 6C4 in d option 0 No, that is not Actually d) is best option among other options upper bound is ok here, problem with lower bound 0 there is no problem u would generate the same sequence by applying nCr = nCn-r which i am talking above 0 Thanks for the explanation. :) 0 Excellent Sachin Sir!! +35 votes Suppose n=4 labeled vertices. Max possible edges = \frac{n(n-1)}{2} = \frac{4*3}{2} = 6 edges At least edges in the graph = \frac{n(n-3)}{2} = \frac{4*1}{2} = at least 2 edges in the graph Total possible number of graphs = {}^{6}C_2 + {}^{6}C_3 + {}^{6}C_4 +{}^{6}C_5 +{}^{6}C_6. As {}^{6}C_2 is same as {}^{6}C_4 because both are same as \frac{6!}{4!2!}, So {}^{n}C_r = {}^{n}C_(n-r) Re write the the above sequence {}^{6}C_2 + {}^{6}C_3 + {}^{6}C_4 +{}^{6}C_5 +{}^{6}C_6 = {}^{6}C_4 + {}^{6}C_3 + {}^{6}C_2 +{}^{6}C_1 +{}^{6}C_0 =$$\sum _{k=0}^{n} \frac{n(n-1)}{2}C_k$$Hence, option (D) is correct! answered by Boss (41.5k points) 0 Correct and fast approach .... 0 This shud b selected as d best answer :) 0 Short and precise 0 @Manu sir Your explanation is very Nice I understand every thing +1 This is better. Examples make problem easier. +1$n=4\$ here

1
2