The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+29 votes
2.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$
asked in Graph Theory by Veteran (59.6k points)
retagged by | 2.9k views

2 Answers

+62 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 (55.4k 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.
+6
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!!
+26 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 (40.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
0
This is better. Examples make problem easier.


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

40,994 questions
47,622 answers
146,898 comments
62,346 users