Let G be a graph with vertices of degrees 1,1,2,3,3,3,4,4,5,8. How many paths of length 2 are there?

any help?

I'd like to see someone answer the second question too :)

---

I do not think I can help with the second question. 

And I do not even understand what you are asking with the first question. (That may or may not be because of my own ignorance)

Answer to the first question:a path of length 2 consists of 3 ordered vetrices, where the first vetrice is connected to the second, and the second vertice is connected to the third (the first vetrice and the third vertice can't be the same vetrice).

In a path of length 2, the second vertice has to be connected to at least 2 other vertices, meaning that the second vetrice's degree has to be at least 2. suppose we have a vetrice v, deg(v)=r>1, to find the number of paths of length 2 where the second vertice is v, we have to find the number of vertices that are connected to v (that's r, by definition) and multiply it by r-1 (so, if we have a vertice with degree r, the number of paths of length 2 where the second vertice is v is r(r-1)).

why? we already know that the second vertice is v, all we have to do is find other 2 vertices, that are connected to the second one. the order of the vertices matters, because one has to be the first vertice (where the path begins) and one has to be the last vertice (where the path ends). we have r vertices to choose from, so we have a total number of r(r-1) combinations.

to find the total number of paths with length 2, we have to find deg(v)*(deg(v)-1) for every vertice v with deg(v)>1, and find the sum of the results.

so the answer should be 2*(2-1)+3*(3-1)+3*(3-1)+3*(3-1)+4*(4-1)+4*(4-1)+5*(5-1)+8*(8-1)=2+6+6+6+12+12+20+56=120

i hope im right 

Here's a graph that conforms to the specified vertices:

I know little or nothing about graph theory, so I wrote a brute force and ignorance program to calculate the number of paths of length 2 here and came up with 77.  However, it wouldn't surprise me if this were wrong!