The Gateway to Computer Science Excellence
+2 votes

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

  1. 1
  2.  1/8  
in Graph Theory by Active (3.6k points)
reshown by | 173 views



Since it is an undirected random graph and not a null graph => it will have an edge

So probability of having an edge in the graph is 1.

But wikipedia says that -->

It may be considered undirected, directed, or even both; when considered as directed, it is a directed acyclic graph. And it is both a complete graph and an edgeless graph. However, definitions for each of these graph properties will vary depending on whether context allows for K 0 {\displaystyle K_{0}} .

So 2 case arise if the graph is null or not.

favourable case is not null.

so probability = 1/2

but since 1/2 is not in option we will go with 1 assuming that they are not taking null graph into consideration.

@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 :)

2 Answers

+4 votes

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.

by Veteran (119k points)

@srestha Thank you.. :)

Why is probability of having an edge in a graph with n vertices is 1 is wrong if it is not a null graph ?
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
0 votes
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, 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
by Active (1.2k points)
edited by
How u getting 28 ?
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,834 questions
57,838 answers
108,336 users