Is it no. of graph with 3 length cycle or different ways in which we can select 3 vertex out of 8 vertex in same graph?

Dark Mode

108 votes

Best answer

**Answer is (C)**

A cycle of length $3$ requires $3$ vertices.

Number of ways in which we can choose $3$ vertices from $8$ = $^{8}C_{3} =56.$

Probability that $3$ vertices form a cycle $=\text{ Probability of edge between vertices 1 and 2}\times \text{ Probability of edge}$

$ \text{between vertices 2 and 3} \times \text{Probability of edge between vertices 1 and 3}$

$=\dfrac{1}{2}\times \dfrac{1}{2}\times \dfrac{1}{2} =\dfrac{1}{8}$

So, expected number of cycles of length $3 = 56\times \dfrac{1}{8} = 7$

[email protected] http://stackoverflow.com/questions/14801072/number-of-cycles-in-a-random-graph

29 votes

Maximum number of cycles of length 3 from 8 vertices = C(8,3) = 56.

It is a Binomial experiment as we keep on repeating the same Bernouli experiment again and again. What Bernouli experiment we keep on repeating ? We keep on checking all 56 possibilities whether there is a cycle or not. Checking is clearly a Bernouli experiment because after checking we will either find cycle (success) or no-cycle(failure).

So number of Bernouli experiments, n = 56.

Let X be a random variable which indicates number of 3-length cycles.

Expectation (X) (i.e) Expected number of 3-length cycles = n * p (since it is a Binomial distribution)

where n is number of Bernouli trials or experiments and p is probability of success (i.e) probability of getting a 3-length cycle in 1 Bernouli experiment. p = 1/8 as there are 8 possibilities of having edges with 3 vertices and only one among them will have 3 edges which form a cycle.

So Expectation (X) = n * p

= 56 * 1/8

= 7.

It is a Binomial experiment as we keep on repeating the same Bernouli experiment again and again. What Bernouli experiment we keep on repeating ? We keep on checking all 56 possibilities whether there is a cycle or not. Checking is clearly a Bernouli experiment because after checking we will either find cycle (success) or no-cycle(failure).

So number of Bernouli experiments, n = 56.

Let X be a random variable which indicates number of 3-length cycles.

Expectation (X) (i.e) Expected number of 3-length cycles = n * p (since it is a Binomial distribution)

where n is number of Bernouli trials or experiments and p is probability of success (i.e) probability of getting a 3-length cycle in 1 Bernouli experiment. p = 1/8 as there are 8 possibilities of having edges with 3 vertices and only one among them will have 3 edges which form a cycle.

So Expectation (X) = n * p

= 56 * 1/8

= 7.

0

edited
Jan 1, 2021
by neel19

@Mantu

Let the 3 vertices are $a, b, c$

The probability of having an edge between a pair of vertices is $1/2$ (Given in Ques) and having an edge between a pair of vertices is an independent event.

$P(ab, bc, ca) = P(ab) * P(bc) * P(ca)$

$= 1/2*1/2*1/2$

$= 1/8$

Hence, out of 8 possibilities, only one will have an edge among all three vertices.

Let the 3 vertices are $a, b, c$

The probability of having an edge between a pair of vertices is $1/2$ (Given in Ques) and having an edge between a pair of vertices is an independent event.

$P(ab, bc, ca) = P(ab) * P(bc) * P(ca)$

$= 1/2*1/2*1/2$

$= 1/8$

Hence, out of 8 possibilities, only one will have an edge among all three vertices.

1

2 votes

Let us solve the problem using indicator random variable.

Given $8$ vertices, the total number of $3$ cycles we can have is $\binom{8}{3}$

Let $X$ be the random variable indicating the number of number of cycles we can have in a random graph.

So $0\leq X \leq \binom{8}{3}$ [Just an observation]

So at most we can have $\binom{8}{3}$ number of $3$ cycles.

Now let us order these $\binom{8}{3}$ cycles from $1$ to $\binom{8}{3}$

Let $X_i$ be the indicator random variable indicating that our graph has $i$th cycle.

i.e. $$X_i = \begin{cases} 1 \text{ if cycle $i$ is in our graph} \\ 0 \text{ otherwise}\end{cases}$$

So, $$X= \sum_{i=0}^{\binom{8}{3}} X_i$$

Taking expection on both sides,

$$E[X]= E\left[ \sum_{i=0}^{\binom{8}{3}} X_i \right]$$

using linearity of expection we have,

$$E[X]= \sum_{i=0}^{\binom{8}{3}} E\left[X_i \right]$$

Now from the property of indicator random variable, we know

$E[X_i]=Pr\{X_i=1\}$

Now we need to find the probability that a particular cycle is included in our graph.

Now suppose $v_1,v_2,v_3$ constitutes a $3$ cycle. Then probability it shall be present in our graph is:

Pr= Probability that edge $v_1-v_2$ is present $\times$ Probability that edge $v_2-v_3$ is present $\times$ Probability that edge $v_1-v_3$ is present

=$\frac{1}{2} \times \frac{1}{2} \times \frac{1}{2} = \frac{1}{8}$

[Note that we consider only the $3$ required edges, and did not consider whether any other edges is present or not, because, our main concern is the cycle $v_1-v_2-v_3-v_1$ and we are concerned about its presence only. We do not care about the presence of other edges. They may be present or might not be present... But we do not care, and hence that probability is $1$...]

So,

$$E[X]= \sum_{i=0}^{\binom{8}{3}} E\left[X_i \right] = \binom{8}{3}*\frac{1}{8}=7$$

Given $8$ vertices, the total number of $3$ cycles we can have is $\binom{8}{3}$

Let $X$ be the random variable indicating the number of number of cycles we can have in a random graph.

So $0\leq X \leq \binom{8}{3}$ [Just an observation]

So at most we can have $\binom{8}{3}$ number of $3$ cycles.

Now let us order these $\binom{8}{3}$ cycles from $1$ to $\binom{8}{3}$

Let $X_i$ be the indicator random variable indicating that our graph has $i$th cycle.

i.e. $$X_i = \begin{cases} 1 \text{ if cycle $i$ is in our graph} \\ 0 \text{ otherwise}\end{cases}$$

So, $$X= \sum_{i=0}^{\binom{8}{3}} X_i$$

Taking expection on both sides,

$$E[X]= E\left[ \sum_{i=0}^{\binom{8}{3}} X_i \right]$$

using linearity of expection we have,

$$E[X]= \sum_{i=0}^{\binom{8}{3}} E\left[X_i \right]$$

Now from the property of indicator random variable, we know

$E[X_i]=Pr\{X_i=1\}$

Now we need to find the probability that a particular cycle is included in our graph.

Now suppose $v_1,v_2,v_3$ constitutes a $3$ cycle. Then probability it shall be present in our graph is:

Pr= Probability that edge $v_1-v_2$ is present $\times$ Probability that edge $v_2-v_3$ is present $\times$ Probability that edge $v_1-v_3$ is present

=$\frac{1}{2} \times \frac{1}{2} \times \frac{1}{2} = \frac{1}{8}$

[Note that we consider only the $3$ required edges, and did not consider whether any other edges is present or not, because, our main concern is the cycle $v_1-v_2-v_3-v_1$ and we are concerned about its presence only. We do not care about the presence of other edges. They may be present or might not be present... But we do not care, and hence that probability is $1$...]

So,

$$E[X]= \sum_{i=0}^{\binom{8}{3}} E\left[X_i \right] = \binom{8}{3}*\frac{1}{8}=7$$