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

option a

option a

Dark Mode

630 views

7 votes

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\}$?

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

5 votes

Best answer

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}$

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}$

1 vote

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

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 vote

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