GATE CSE 2004 | Question: 79

Question

How many graphs on $n$ labeled vertices exist which have at least $\frac{(n^2 - 3n)}{ 2}$ edges ?

• A. $^{\left(\frac{n^2-n}{2}\right)}C_{\left(\frac{n^2-3n} {2}\right)}$
• B. $^{{\large\sum\limits_{k=0}^{\left (\frac{n^2-3n}{2} \right )}}.\left(n^2-n\right)}C_k$
• C. $^{\left(\frac{n^2-n}{2}\right)}C_n$
• D. $^{{\large\sum\limits_{k=0}^n}.\left(\frac{n^2-n}{2}\right)}C_k$

Comments

great work and a best example of multidisclinary question of gate!!!

---

We know that a n vertex graph can have maximum of n(n-1)/2 edges

Now, we want those graphs who have atleast (n^2-3n)/2 edges

or we can say we want those graphs who can reject atmost n(n-1)/2 – (n^2-3n)/2 edges

                                                                                               =2n/2 = n edges

therefore our problem get reduced to finding number of graphs with n vertices who reject almost n edges

n(n-1)/2C0 + n(n-1)/2C1 + …………. +n(n-1)/2Cn

(d) sumation (k=0 to n) {n(n-1)/2Ck)

Answer 1

We have $n$ labeled vertices, so maximum number of edges we can have is $C(n, 2) = $$\frac{n\cdot( n - 1)}{2}$

We need to have at least $\frac{n^2 - 3n}{2}$ edges, so we can remove at most :

$=\frac{n \cdot (n - 1)}{2} - \frac{(n^2 - 3n)}{2} = \frac{n^2 - n}{2} - \frac{(n^2 - 3n)}{2}$

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

So we can remove at most $n$ edges.

 

We can remove $k$ edges in $C(\frac{n\cdot( n - 1)}{2}, k)$ ways by choosing which $k$ vertices to remove from $\frac{n\cdot( n - 1)}{2}$ vertices

Removing no edges from graph = $C(\frac{n\cdot( n - 1)}{2}, 0)$

Removing one edge from graph = $C(\frac{n\cdot( n - 1)}{2}, 1)$

Ans so on up until n.

 

We can write it as :

$=C(\frac{n\cdot( n - 1)}{2}, 0) + C(\frac{n\cdot( n - 1)}{2}, 1) + C(\frac{n\cdot( n - 1)}{2}, 2) + … + C(\frac{n\cdot( n - 1)}{2},n)$

$=\sum_{k = 0}^{n}C(\frac{n\cdot( n - 1)}{2}, k)$

 

Which is (option D)

 

Answer 2

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.

Answer 3

Number of edges in complete graph with n vertices = n(n-1)/2

n(n-1)/2 -n(n-3)/2=n

So this means that I just have the option of choosing another n vertices apart from the n(n-3)/3 which I must compulsorily have (graph must have at least this many vertices)

So i can choose 0,1,2,3,4,5...n from the total n(n-1)/2 vertices and summing them us gives the answer.

so (D) is the answer

Answer 4

I will try to tell the answer in short

the total edges the graph can have is n(n−1)/2.  Let it be T. 

so T= n(n−1)/2

now the graph needs to have atleast n(n−3)/2. Let it be k.

so k=n(n−3)/2

now we can have (k)or (k+1) or (k+2) or (k+3) or (k+4) or ...…..or n(n-1)/2 edges selected from T.

Thus applying combination and doing summation. Also remember the formula nCr = nCn-r

it will directly give option D as answer