The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+37 votes

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$
asked in Graph Theory by Veteran (59.8k points)
retagged by | 3.8k views

2 Answers

+73 votes
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) + \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 (59.8k points)
edited by
@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.
lol, In exam this question is not meant to solve in this way.
We should take small value of n and check options.


#plz explain i am not understand solution which is selected best ??

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
But option D) considers


that means it also considers $\binom{6}{0}+\binom{6}{1}$ which should not be there as per question

maximum upper bound equals to n = 4 so u would stop your expansion up to  6C4  in d option
No, that is not

Actually d) is best option among other options

upper bound is ok here, problem with lower bound
there is no problem u would generate the same sequence by applying nCr = nCn-r which i am talking above
Thanks for the explanation. :)
Excellent Sachin Sir!!
+45 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.7k points)
Correct and fast approach ....
This shud b selected as d best answer :)
Short and precise
@Manu sir

Your explanation is very Nice

I understand every thing
This is better. Examples make problem easier.
$n=4$ here
This should be the best answer !

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,397 questions
53,564 answers
70,837 users