3.9k 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.9k 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) + \ldots +C(a,a)$

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

$= C(a,n) + C(a,n-1) + C(a,n-2) + \ldots +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) + \ldots +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 (59.9k points) edited by 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!! 0 C(a,b) .??? i am not familiar with this notation . Please help . and also refer a good book/resource to get comfortable with Pnc for GATE +1 It means ^aC_b i.e. combinations. You can refer sheldon ross or keneth rosen 0 Even option B we can eliminate as it say at most (N^2 -3N)/2 edges.And option A and C not correct as it refer selecting a particular edge so option D correct. +50 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 (42.4k points) 0 Correct and fast approach .... 0 This shud b selected as d best answer :) 0 Short and precise +1 @Manu sir Your explanation is very Nice I understand every thing +1 This is better. Examples make problem easier. +1$n=4$here 0 This should be the best answer ! 0 ## "At least edges in the graph = n(n−3)2" any one please explain this? 0 votes You can also use some intuition after looking at the answers as to what the final answer should look like, and see if you can get one of the answers. Since the maximum number of edges in a simple graph is$\frac{n^{2} - n}{2}$, and we want atleast$\frac{n^{2} - 3n}{2}$edges, this will be a sum of terms. We select$\frac{n^{2} - 3n}{2}$edges, OR$\frac{n^{2} - 3n}{2} + 1$edges, OR... uptill the maximum of$\frac{n^{2} - n}{2}$edges. So the answer should look like$\sum_{T=\frac{n^{2} - 3n}{2}}^{\frac{n^{2} - n}{2}} (_{T}^{upper}\textrm{C})$where upper is${\frac{n^{2} - n}{2}}$, as defined above. But we see that none of the answers looks exactly like this. The closest answers are B and D. If you've done P & C from Rosen, you'll find this technique of shifting the summation in the generating functions section. So let's try to shift the summation in our answer to see if it can match any of the possible answers. Note that B cannot be the answer because it says the upper limit of summation is what the lower limit should be, and the combinatorial term is also wrong (we want to select from a max of$\frac{n^{2} - n}{2}$edges). So let's try out D. Set$k$such that when$T = \frac{n^{2} - 3n}{2}$, then$k = 0$. So clearly$k = T - \frac{n^{2} - 3n}{2}$. Now when$T = \frac{n^{2} - n}{2}$, then$k$must be$n$. Do we get this?$k = T - \frac{n^{2} - 3n}{2}k = \frac{n^{2} - n}{2} - \frac{n^{2} - 3n}{2}k = \frac{n^{2} - n - n^{2} + 3n}{2}k = n\$

So we have successfully shifted the summation on our answer to match one of the answers given. Answer is D.

edited by

1
2