GateForum Question Bank :Graph Theory

Question

What is the probability that there is an edge in an undirected random graph having 8 vertices?

1. 1
2.  1/8  

Comments

@srestha please explain

It is asking if there is an edge in the undirected graph just like what is probability of getting sunday in a week.

---

same type ques in GATE

---

@Satbir Thanks :)

Answer 1

Probability of taking $0$ vertex among $8$ vertices is $^{8}\textrm{C}_{0}$ [means no edge]

Probability of taking $1$ vertex among $8$ vertices is $^{8}\textrm{C}_{1}$ [means no edge]

Probability of taking $2$ vertex among $8$ vertices is $^{8}\textrm{C}_{2}$ [means $1$ edge]

.......

Now we can take any number of edges

So, number of vertices we can select=$^{8}\textrm{C}_{0}+^{8}\textrm{C}_{1}+^{8}\textrm{C}_{2}+^{8}\textrm{C}_{3}+............+^{8}\textrm{C}_{8}=2^{8}$ 

But according to question there is an edge with $8$ vertices , i.e. $^{8}\textrm{C}_{2}$

So, answer should be $\frac{^{8}\textrm{C}_{2}}{2^{8}}$

---

If they asking for Expected value, then there must be a weight or cost (like 1/2 given in GATE question). But, here that is not the scenario.

https://gateoverflow.in/1535/gate2013-24

https://www.quora.com/What-is-the-difference-between-probability-and-expectation

Comments

If provided that the graph is not null then it will absolutely be fine...But the they have not stated such..

---

Yes right

So here there are 2 cases
1. graph can be null graph(it does not have any edge)
2. graph is not a null graph(it has an edge)

so 1/2 is the answer.
What is wrong in this ?

---

non-NULL graph that can contain any number of edge.

So, if u take probability$\frac{NON-NULL}{NON-NULL+NULL}$ , then NON_NULL  doesnot specifies only $1$ edge among $8$ vertices

Answer 2

As said the answer is 1

But it's not right as the probability will be 2^28 -1 / 2^28 which is close to 1 but not one. The question does not specify Whether the graph chosen will be null or not thus total possibilities =2^28, only.one possibility when edge will not exist if it becomes null graph . So favourable events =2^28-1

. Thus probability becomes 2^28-1/28

Edit its 2^28 not 28

Comments

How u getting 28 ?