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

2 Answers

+48 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 (53.7k points)
edited by

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.

@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.

@ARJUN SIR

#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

$\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?
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. :)
+17 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 Veteran (43.6k 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.


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

33,687 questions
40,231 answers
114,271 comments
38,801 users