The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+39 votes
4k 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 | 4k views

3 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) + \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
+1
How you read the qn? :P
+1
I read it by zooming in :P
+1

How $a-b=n$?

+8

$a = \frac{n^{2} - n}{2} , b= \frac{n^{2} - 3n}{2}$

$a-b = \frac{n^{2}}{2} - \frac{n}{2} - \frac{n^{2}}{2} + \frac{3n}{2} = \frac{2n}{2} = n$

0
plz tell what is wrong in my logic since we need to have at least $n^2-3n/2$ edges and maximum no of edges are $n^2-n/2$ so we can first choose $n^2-3n/2$ edges and then we will have a remaining choice of $n$ edges which we can choose by doing nCn,

So according to me answer should be option A ,plz correct my logic.
+1
Is it a normal level question.. Omg.. ! I feel it really hard to solve .
0
Wow...How do u even think this way
0
how many graph can be formed with exactly (n*n - 3*n)/2 edges, having  n labelled vertices,
0
@Indrajeet ... total no of graph formed with exactly b edges, where total no of vertices in the graph is n = no of ways we can select b edges among n edges. = C (n, b). and here b = (n*n - 3*n)/2 edges.
+1
for example if we have 4 labelled vertices and 2 edges then how many graph can be formed using this??
+1
see .. if no of vertices = n then the graph can have maximum n(n-1)/2 edges.

So if you want graph with only m edges then total possible graphs = no of ways we can choose m edges among n(n-1)/2 edges =C ( n(n-1)/2  , m).

now put n=4 and m=2

graphs possible = 6C2 = 15.
+30

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.

+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.
+7
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!!
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.
+52 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.7k 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 (197 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
49,833 questions
54,800 answers
189,505 comments
80,724 users