# Given graph G, find # of paths of lengh 2

I'm solving this graph theory problem:

Let $$G$$ be a graph on $$10$$ vertices of degrees $$1,1,2,3,3,3,4,4,5,8$$. How many paths of length $$2$$ does $$G$$ contain?

(Reminders: A path of length $$2$$ from vertex $$a$$ to vertex $$b$$ is defined as a sequence of two edges $$a\text{---}v$$ and $$v\text{---}b$$, where $$v$$ is some vertex. We do not require $$a$$ and $$b$$ to be distinct. If $$a$$ and $$b$$ are distinct, then the path $$a\text{---}v\text{---}b$$ is considered distinct from the path $$b\text{---}v\text{---}a$$.)

I'm not sure where to start. I've tried to list paths, but there is some overlap, and the graph is too big to draw. How should I approach this problem?

Thanks.

• I'm assuming that the edges need to be distinct, and that this isn't a simple graph? Nov 3, 2015 at 2:31
• $a--v--a$ would count as a path if thats what your asking.. Nov 3, 2015 at 2:38

HINT: Each edge of $G$ contributes two out-and-back paths of length $2$. Each path of length $2$ that is not out-and-back has a vertex at its midpoint that it enters by one edge and leaves by another; thus, each vertex of degree greater than $1$ and each pair of edges incident at that vertex give rise to two more paths of length $2$, one in each direction.
• @BrianM.Scott Is the answer $64$? Nov 7, 2016 at 20:13
Let $$v$$ be a vertex of $$G$$, and let $$d$$ be the degree of $$v$$. Then there are $$d^2$$ paths of the form $$a\text{---}v\text{---}b$$, because there are $$d$$ choices for vertex $$a$$ and $$d$$ choices for vertex $$b$$.
Therefore, if the vertices of $$G$$ have degrees $$d_1,d_2,\ldots,d_n,$$ then the number of paths of length $$2$$ is $$d_1^2+d_2^2+\cdots+d_n^2$$. In this case, that number is $$1^2+1^2+2^2+3^2+3^2+3^2+4^2+4^2+5^2+8^2=\boxed{154}.$$