02 - Walks

Walk

Let $G$ be a graph then

Walk $W$ is sequence

$$v_0{v}_1\cdots v_t\text{ where }{v}_i\in G$$

such that

$$v_i{v}_{i+1}\in E\text{ for all }i=0,1,\cdots ,t-1$$

where length of walk is denoted by number of steps $t$

Note that the vertices don’t have to be necessarily distinct

$x-y$ walk Suppose $x=v_0$ and $y=v_t$ then

Walk from $x$ to $y$ is $x-y$ walk

Path

Let $G$ be a graph then

Path in $G$ is a walk where $v_0,\cdots ,v_t$ are distinct

Closed Walk

Let walk $W$ be of graph $G$

Walk $W$ is closed if

$$v_t=v_0$$

Cycle

Let walk $W$ be of graph $G$ defined by

$$v_1{v}_2\cdots v_t$$

Then $v_1{v}_2\cdots v_t$ is a cycle in $G$ if and only if

1. $t\ge 3$
2. $v_1,\cdots ,v_t$ are distinct vertices of $G$
3. $v_1{v}_2,\cdots ,v_{t-1}{v}_t,v_t{v}_1$ are edges of $G$

Equivalency of Walks and Paths in Graphs lemma

Let $G$ be a graph
Let $x,y\in V(G)$ then

$G$ contains an $x-y$ walk $⟺$ $G$ contains a $x-y$ path

Proof

Any path is a walk so $⟸$ is trivial

Suppose $G$ contains $x-y$ walk so let

$$v_0\cdots v_t$$

be shortest $x-y$ walk in $G$

If $v_i=v_j$ for some $i<j$ then construct shorter $x-y$ walk

$$v_0\cdots v_i{v}_{j+1}\cdots v_t$$

where if $j=t$ then use $v_0\cdot v_i$

Hence as all vertices in walk are now distinct then it is a path

Connected Vertices

Let $G$ be a graph
Let $x,y\in V(G)$

$x,y$ are connected in $G$ if

$$G\text{ contains }x-y\text{ walk / path}$$

Euler Trail

Let $G$ be a graph then
Let $W=v_0\cdots v_t$ in $G$ be a walk where each edge of $G$ is used exactly once

$W$ is an Euler Tour / Euler Circuit if

$$v_0=v_t$$