10,342 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$

### 1 comment

great work and a best example of multidisclinary question of gate!!!

## 7 Answers

Best answer

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). ### 4 Comments It means ^aC_b i.e. combinations. You can refer sheldon ross or keneth rosen edited 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. No need to shuffle the nodes within after edges are selected? n! ways to shuffle a graph once we have the edges fixed (labelled vertices)? 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! ### 4 Comments ## "At least edges in the graph = n(n−3)2" any one please explain this? 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) Easy approach . Loved it. For n = 1, we need at least -1 edges. This seems troublesome, take some other value. For n = 2, we need at least -1 edges. Again, take some other value. For n = 3, we need at least 0 edges. So, such graphs possible for 3 vertices are:-$1 + 3 +3+1$(for 0 edges, for 1 edge, for 2 edges and for 3 edges respectively) =>$8$Look at Option D. It is:${^3C_0} + {^3C_1} + {^3C_2} + {^3C_3}$=>$1 + 3 +3+1$=>$8\$

This is the best explanation I can provide to you

by
Answer:

62 votes
12 answers
1
26,818 views
31 votes
5 answers
2
9,731 views
58 votes
9 answers
3
2 votes
2 answers
4
1,867 views