Title: Theory / Unimportant / CS / Fundamental / Graph / Bondy - Murty / 03 Connected

Name: A walk in \(G\)
Definition: A sequence of the form \(v_0e_1v_1\dots v_{\ell-1}e_\ell v_\ell\) such that \(e_i=\{v_{i-1}v_i\}\)
Page: 79
Chapter: 3
Section: 1
Variables: \((G,E)\) a graph
Denoted by: \(W\)

Question: \(W\) is counted
Answer: \(2^i\) times, where \(i\) is the number of loops in the walk
Page: 79
Chapter: 3
Section: 1
Variables: \((G,E)\) a graph
\(W=v_0e_1v_1\dots v_{\ell-1}e_\ell v_\ell\) a walk

Name: A walk connecting \(x\) and \(y\)
Definition: A walk \(v_0e_1v_1\dots v_{\ell-1}e_\ell v_\ell\) with \(x=v_0\) and \(y=v_\ell\)
Page: 79
Chapter: 3
Section: 1
Variables: \((G,E)\) a graph
Name2: An \(xy\)-walk

Name: The initial vertex of \(W\)
Definition: \(v_0\)
Page: 79
Chapter: 3
Section: 1
Variables: \((G,E)\) a graph
\(W=v_0e_1v_1\dots v_{\ell-1}e_\ell v_\ell\) a walk

Name: The terminal vertex of \(W\)
Definition: \(v_\ell\)
Page: 79
Chapter: 3
Section: 1
Variables: \((G,E)\) a graph
\(W=v_0e_1v_1\dots v_{\ell-1}e_\ell v_\ell\) a walk

Name: internal vertex of \(W\)
Definition: \(v_i\) for \(0<i<\ell\)
Page: 80
Chapter: 3
Section: 1
Variables: \((G,E)\) a graph
\(W=v_0e_1v_1\dots v_{\ell-1}e_\ell v_\ell\) a walk

Name: The length of \(W\)
Definition: \(\ell\)
Page: 80
Chapter: 3
Section: 1
Variables: \((G,E)\) a graph
\(W=v_0e_1v_1\dots v_{\ell-1}e_\ell v_\ell\) a walk

Name: An \(x\)-walk
Definition: A walk \(W=v_0e_1v_1\dots v_{\ell-1}e_\ell v_\ell\) with \(x=v_0\)
Page: 80
Chapter: 3
Section: 1
Variables: \((G,E)\) a graph

Name: The segment of \(W\) from \(v_i\) to \(v_j\)
Definition: The subsequences starting at \(v_i\) and ending at \(w_j\)
Page: 80
Chapter: 3
Section: 1
Variables: \((G,E)\) a graph
\(W=v_0e_1v_1\dots v_{\ell-1}e_\ell v_\ell\) a walk
\(0\le i\le j\le \ell\)
Notation: \(v_iWv_j\)

Name: The segment of \(W\) from \(v_i\) to \(v_j\)
Definition: The unique walk \(W=v_0e_1v_1\dots v_{\ell-1}e_\ell v_\ell\)
Page: 80
Chapter: 3
Section: 1
Variables: \((G,E)\) a graph
Notation: \(v_i\dots v_\ell\)
Assuming: \(G\) is simple

Name: A closed walk
Definition: A \(xx\)-walk for some vertex \(x\)
Page: 80
Chapter: 3
Section: 1
Variables: \((G,E)\) a graph

Name: A trail
Definition: A walk with pairwise distinct edges
Page: 80
Chapter: 3
Section: 1
Variables: \((G,E)\) a graph