recategorized by
1,016 views
8 votes
8 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\}$?

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

5 Answers

Best answer
5 votes
5 votes
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}$
selected by
1 votes
1 votes
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 votes
1 votes
Total triangles possible via given strategy = 4.

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

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)

Answer:

Related questions