1
$\begingroup$

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.

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

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ What do out-and-back paths mean? $\endgroup$ Nov 3, 2015 at 2:44
  • 1
    $\begingroup$ @Mark: Just what it sounds like: a path that starts at some vertex, goes to another, and returns along the same edge. $\endgroup$ Nov 3, 2015 at 2:46
  • $\begingroup$ I got the answer, thanks a lot! $\endgroup$ Nov 3, 2015 at 3:14
  • 1
    $\begingroup$ @Mark: Excellent; you’re welcome! $\endgroup$ Nov 3, 2015 at 3:15
  • $\begingroup$ @BrianM.Scott Is the answer $64$? $\endgroup$
    – Dreamer
    Nov 7, 2016 at 20:13
1
$\begingroup$

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}.$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .