630 views

Consider the graph shown below:

The following experiment is performed using this graph. First, an edge $e =\{i,j\}$ of the graph is chosen uniformly at random from the set of $9$ possibilities. Next, a common neighbour $k$ of $i$ and $j$ is chosen, again uniformly from the set of possibilities. (Note that the set of possibilities is always non-empty.) Thus, $\{i, j, k\}$ is a triangle in the graph. What is the probability that the triangle finally picked is $\{1, 2, 3\}$?

1. $\frac{1}{6}$
2. $\frac{1}{4}$
3. $\frac{1}{3}$
4. $\frac{2}{3}$
5. $\frac{5}{6}$

### 1 comment

3*1/9*1/2 = 1/6

option a

First we select edge 1-3 with probability $\frac{1}{9}$ now common neighbor of (1,3) are (4,2)

Probability of choosing 2 as neighbor is so that {1,2,3} can from triangle is $\frac{1}{2}$ so total probabiltiy is $\frac{1}{9}*\frac{1}{2}$

similar for edge 1-2 and edge 2-3 as both have only 2 neighbour common {3,5} and {1,6} respectively

total probability is $\frac{1}{9}*\frac{1}{2}*3$= $\frac{1}{6}$
by
Triangle 1 2 3 can be formed in the following manner

You pick edge 12 and then the common vertex 3 OR you pick edge 13 and then the common vertex 2 OR you pick the edge 23 and then the common vertex 1

= 1/9*1/2 + 1/9*1/2 + 1/9*1/2

= 1/6

For every selection of an edge we will have two possibility of choosing a common vertex, only one of them will be the correct choice

### 1 comment

thanks a lot...
Total triangles possible via given strategy = 4.

Probability of (1,2,3) = 1/4.
by

### 1 comment

Hello Aghori

why do you think all triangle have same probability of getting select like 1/4 each ?

For the 6 edges (1,4) , (1,5) , (3,4) , (2,5) , (3,6) , (2,6) , we have only 1 option for neighbour after selecting them, For the remaining 3 edges, we have 2 options each,

So (6/9) * (1/8) + (3/9) * (2/8) = 1/6 (Option A)

### 1 comment

edited
Hello chandrashis

how 1/8 and 2/8?

i'm not getting exactly what you're doing.