# More Graph Questions

Printable View

• Apr 6th 2008, 03:01 PM
shawn
More Graph Questions
Thanks in advance!
• Apr 6th 2008, 04:21 PM
Plato
You do know, I hope, that these definitions are not unique or standard.
So if we mean by a walk a sequence of alternating vertices and edges, beginning with a vertex and ending with a vertex, not necessarily the same.
A path is a walk in which all edges are distinct.
(Again these may not agree with your definitions)

So is a star-like graph with n+1 vertices, 0 to n, both “010” and “102” are walks but only “102” is a path.

Thus the number of walks of length two is ${\binom {n} {2}} + n$. WHY?
But the number of paths of length two is ${\binom {n} {2}}$. WHY?
• Apr 6th 2008, 07:10 PM
shawn
Quote:

Originally Posted by Plato
You do know, I hope, that these definitions are not unique or standard.
So if we mean by a walk a sequence of alternating vertices and edges, beginning with a vertex and ending with a vertex, not necessarily the same.
A path is a walk in which all edges are distinct.
(Again these may not agree with your definitions)

So is a star-like graph with n+1 vertices, 0 to n, both “010” and “102” are walks but only “102” is a path.

Thus the number of walks of length two is ${\binom {n} {2}} + n$. WHY?
But the number of paths of length two is ${\binom {n} {2}}$. WHY?

Your interpretation is correct.

The number of walks of length two is ${\binom {n} {2}} + n$ because you either just choose two edges from n (all the paths) or you can walk from 0 to any vertex and back and there are n ways to do this.

and the number of paths of length two is ${\binom {n} {2}}$ because you just choose two edges from n and because they are all adjacent through 0 you have your path.
• Apr 7th 2008, 03:32 PM
Plato
Please do not use PM's to ask for more help!

If n=4 then $Adj = \left( {\begin{array}{*{20}c} 0 & 1 & 1 & 1 & 1 \\
1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 1 \\
1 & 1 & 1 & 1 & 0 \\\end{array}} \right)$

$\left( {Adj} \right)^2 = \left( {\begin{array}{*{20}c}
4 & 3 & 3 & 3 & 4 \\ 3 & 4 & 3 & 3 & 4 \\ 3 & 3 & 4 & 3 & 4 \\
3 & 3 & 3 & 4 & 4 \\ 4 & 4 & 4 & 4 & 5 \\\end{array}} \right)$
• Apr 7th 2008, 03:39 PM
shawn
Quote:

Originally Posted by Plato
Please do not use PM's to ask for more help!

If n=4 then $Adj = \left( {\begin{array}{*{20}c} 0 & 1 & 1 & 1 & 1 \\
1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 1 \\
1 & 1 & 1 & 1 & 0 \\\end{array}} \right)$

$\left( {Adj} \right)^2 = \left( {\begin{array}{*{20}c}
4 & 3 & 3 & 3 & 4 \\ 3 & 4 & 3 & 3 & 4 \\ 3 & 3 & 4 & 3 & 4 \\
3 & 3 & 3 & 4 & 4 \\ 4 & 4 & 4 & 4 & 5 \\\end{array}} \right)$

Thank you good sir, sorry about the PM.