Tzur

04-13-2012, 05:57 AM

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