4.3k 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 | 4.3k 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). by Veteran (60.4k points) edited by +1 How you read the qn? :P +1 I read it by zooming in :P +1 How a-b=n? +8 a = \frac{n^{2} - n}{2} , b= \frac{n^{2} - 3n}{2} a-b = \frac{n^{2}}{2} - \frac{n}{2} - \frac{n^{2}}{2} + \frac{3n}{2} = \frac{2n}{2} = n 0 plz tell what is wrong in my logic since we need to have at least n^2-3n/2 edges and maximum no of edges are n^2-n/2 so we can first choose n^2-3n/2 edges and then we will have a remaining choice of n edges which we can choose by doing nCn, So according to me answer should be option A ,plz correct my logic. +1 Is it a normal level question.. Omg.. ! I feel it really hard to solve . 0 Wow...How do u even think this way 0 how many graph can be formed with exactly (n*n - 3*n)/2 edges, having n labelled vertices, 0 @Indrajeet ... total no of graph formed with exactly b edges, where total no of vertices in the graph is n = no of ways we can select b edges among n edges. = C (n, b). and here b = (n*n - 3*n)/2 edges. +1 for example if we have 4 labelled vertices and 2 edges then how many graph can be formed using this?? +2 see .. if no of vertices = n then the graph can have maximum n(n-1)/2 edges. So if you want graph with only m edges then total possible graphs = no of ways we can choose m edges among n(n-1)/2 edges =C ( n(n-1)/2 , m). now put n=4 and m=2 graphs possible = 6C2 = 15. +33 If I straight away do this question then it should be - {\sum_{k=\frac{n^2-3n}{2} }^\frac{n^2-n}{2}} {{\frac{n^2-n}{2}}\choose{k}}, None of the option matches. Therefore I need to modify this little bit to come up in the same format of one of the option. (See, Option A and C are out of consideration. A is the number of graphs with exactly equal to \frac{n^2-3n}{2} edges. And Option C is the number of graphs with exactly equal to n edges ). Once you realize one identity then this problem is handy to u- \sum_{k=r}^n \binom{n}{k} = \sum_{k=0}^{n-r} \binom{n}{k} (to prove this- see, first term of LHS is same as last term of RHS and 2nd term equate to 2nd last term of RHS and so on. And number of terms in LHS and RHS are same i.e. n-r) Using this, we can see {\sum_{k=\frac{n^2-3n}{2} }^\frac{n^2-n}{2}} {{\frac{n^2-n}{2}}\choose{k}} = {\sum_{k=0 }^n} {{\frac{n^2-n}{2}}\choose{k}} Hence Option D is matching. And it is not hard to proof. +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. +8 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!! 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. +71 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! by Boss (43.5k points) +1 Correct and fast approach .... +1 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 It means that the minimum number of edges should be n(n-3)/2 and atmost n(n-1)/2(max. no of edges in a graph) 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.

by (443 points)
edited by