3.2 Walks

Types of Graph Walks

A walk of length $k-1$ in an undirected graph is a sequence of edges
$S=\{v_1,v_2\},\{v_2,v_3\},\dots ,\{v_{k-1},v_k\},$
where each $v_i$ is a (not necessarily distinct) vertex in the graph, and each pair $\{v_i,v_{i+1}\}$ represents an edge between consecutive vertices.

Several important concepts in graph theory are special types of walks defined by additional constraints:

• A closed walk is a walk that starts and ends at the same vertex (i.e.,$v_1=v_k$).
• A trail is a walk in which no edge is repeated, although vertices may be revisited.
  • A path is a trail in which no vertex is repeated, meaning all vertices and edges are distinct.
    • A cycle is a closed path, where the walk starts and ends at the same vertex, and no other vertex or edge is repeated.
  • A circuit (or tour) is a closed trail, meaning it starts and ends at the same vertex without repeating any edges.

These definitions form a hierarchy: every path is a trail, every trail is a walk, and every cycle is both a path and a circuit:

Furthermore, an Eulerian walk (or trail, circuit, etc.) is a walk that traverses every edge of the graph exactly once, whereas a Hamiltonian walk (or path, cycle, etc.) is a walk that visits every vertex of the graph exactly once. These are both more strictly constrained cases of the more general concepts defined above.

Properties

(Eulerian Walk) An undirected graph has an Eulerian walk if and only if the graph is connected, and there are exactly 0 or 2 odd-degree vertices.

(Eulerian Tour) An undirected graph has an Eulerian tour if and only if the graph is connected, and for all $v\in V$, $\mathrm{deg}v=2k$ for some $k$.

In other words, the requirements for an Eulerian tour are that the graph is connected and each vertex has an even degree. Let’s go ahead and prove this using induction:

• Base Case: the only graph with 3 vertices that has an Eulerian tour is $K_3$ (complete graph).
• Hypothesis: assume that

Examples

Eulerians

Consider the following graph:

\begin{document}
 
\begin{tikzpicture}[scale=1.5, every node/.style={circle, fill=black, inner sep=1.5pt}]
 % Define positions
 \node (1) at (0,0) {};
 \node (2) at (1,1) {};
 \node (3) at (1,-1) {};
 \node (4) at (3,0) {};
 \node (5) at (5,1) {};
 \node (6) at (5,-1) {};
 \node (7) at (6,0) {};
 
 % Draw edges (left diamond)
 \draw (1) -- (2);
 \draw (1) -- (3);
 \draw (2) -- (3);
 \draw (1) -- (4);
 \draw (2) -- (4);
 \draw (3) -- (4);
 
 % Draw edges (right diamond)
 \draw (4) -- (5);
 \draw (4) -- (6);
 \draw (5) -- (6);
 \draw (4) -- (7);
 \draw (5) -- (7);
 \draw (6) -- (7);
 
 % Draw top and bottom connections
 \draw (2) -- (5);
 \draw (3) -- (6);
 
 % Labels
 \node[draw=none, fill=none, above left=2pt] at (1) {1};
 \node[draw=none, fill=none, above=2pt] at (2) {2};
 \node[draw=none, fill=none, below=2pt] at (3) {3};
 \node[draw=none, fill=none, above=2pt] at (4) {4};
 \node[draw=none, fill=none, above=2pt] at (5) {5};
 \node[draw=none, fill=none, below=2pt] at (6) {6};
 \node[draw=none, fill=none, right=2pt] at (7) {7};
 
\end{tikzpicture}
 
\end{document}

Is there an Eulerian tour in the graph above? If no, give justification. If yes, provide an example. $1$ and $7$ have an odd degree of $3$, the graph does not have an Eulerian tour.

Since vertices

Is there an Eulerian walk in the graph above? If no, give justification. If yes, provide an example.