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

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

Comments

It means $^aC_b$ i.e. combinations.

You can refer sheldon ross or keneth rosen

---

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.

---

No need to shuffle the nodes within after edges are selected? $n!$ ways to shuffle a graph once we have the edges fixed (labelled vertices)?

Answer 2

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!

Comments

"At least edges in the graph = n(n−3)2"

any one please explain this?

---

It means that the minimum number of edges should be n(n-3)/2 and atmost n(n-1)/2(max. no of edges in a graph)

---

Easy approach . Loved it.

Answer 3

For n = 1, we need at least -1 edges. This seems troublesome, take some other value.

For n = 2, we need at least -1 edges. Again, take some other value.

For n = 3, we need at least 0 edges.

So, such graphs possible for 3 vertices are:-

$1 + 3 +3+1$ (for 0 edges, for 1 edge, for 2 edges and for 3 edges respectively) => $8$

 

Look at Option D. It is:

${^3C_0} + {^3C_1} + {^3C_2} + {^3C_3}$

=> $1 + 3 +3+1$ => $8$

Answer 4

This is the best explanation I can provide to you