Let $G=(V,E)$ be a graph.

Walks

• A walk in $G$ is a sequence of vertices $\{v_1,v_2,v_3,...,v_n\}$ in $V(G)$, such that each consecutive pair of vertices in the walk $\{v_i,v_{i+1}\}$ , form an edge in $E(G).$
  • The length of a walk is the number of steps, i.e. the number of edges in the walk.
  • no restrictions, can have $\mathrm{\infty }$ length
  • Edge and Vertices both can be repeated.

Path

• A path in $G$ is a walk where no vertices are repeated
  • edges can be repeated

Trails

• A trail is a walk where no edges are repeated
  • vertices can be repeated

Cycles

• A cycle in $G$ is a walk with $\mathrm{length}\ge 3,$ where the first and last vertex are the same, but no other vertices are the same.
  • loop
  • $C_n$ is bipartite $⟺$ n is even, for $n\ge 3$
  • if $G$ contains an odd cycle, then $G$ is not bipartite

Concatenation

• Two walks can be concatenated by concatenating their respective sequences.
• If walks $W=\{v_1,v_2,v_3,...,v_n\},K=\{u_1,u_2,u_3,...,u_m\}$ their concatenation $WK=\{v_1,v_2,v_3,...,v_n,u_1,u_2,u_3,...,u_m\}$.
  • Note that order of concatenation matters, it is not a commutative operation
• might not be a path if there are repeated vertices