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

3 Answers

+75 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) + \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 (60k points)
edited by
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.
+55 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 (42.8k points)
0
Correct and fast approach ....
0
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 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 (231 points)
edited by
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
50,092 questions
55,291 answers
190,810 comments
86,116 users