Hi All!
Let G = (V,E) be a graph with n vertices and m >= 1.5n edges. Prove that there are at least (4m^3)/(27n^2) simple paths of length three, i.e., simple paths of the form a,b,c,d such that (a,b),(b,c),(c,d) are in E, where a, b, c, d are four distinct vertices.
Here is what i got so far: (hope I'm in the right direction)
X will be the random variable that counts the number of paths of length 3 in G.
I want to show that the E(x)=(4m^3)/(27n^2)
and this will solve the problem. (Am I right?)
X should be a sum of indicator random variables of all the permutations of length 4 of {1,2, .... , n}. and then using the linearity of the expectation to calculate the above.
should I randomly pick a permutation of size 4? how can calculate the expectation (Probability in case of indicator random variable)?
Any help will be appreciated
Let G = (V,E) be a graph with n vertices and m >= 1.5n edges. Prove that there are at least (4m^3)/(27n^2) simple paths of length three, i.e., simple paths of the form a,b,c,d such that (a,b),(b,c),(c,d) are in E, where a, b, c, d are four distinct vertices.
Here is what i got so far: (hope I'm in the right direction)
X will be the random variable that counts the number of paths of length 3 in G.
I want to show that the E(x)=(4m^3)/(27n^2)
and this will solve the problem. (Am I right?)
X should be a sum of indicator random variables of all the permutations of length 4 of {1,2, .... , n}. and then using the linearity of the expectation to calculate the above.
should I randomly pick a permutation of size 4? how can calculate the expectation (Probability in case of indicator random variable)?
Any help will be appreciated