Walks, Trees & Isomorphism

Connectivity, Traversals, and Graph Measures

1. Walks, Trails & Paths

Definitions

  • Walk An alternating sequence of vertices and edges $\langle v_0, e_1, v_1, ..., v_n \rangle$.
    Length: Number of edges (steps).
    Closed: Starts and ends at same vertex.
    Trivial: Length 0 (single vertex).
  • Trail A walk with no repeated edges.
  • Path A trail with no repeated vertices (except start/end).

Interactive Analysis

y z x u v w

2. Connectivity

Connected Graph

For every pair of vertices $u, v$, there exists a walk between them. Disconnected graphs are made of components.

Distance $d(u,v)$

The length of the shortest path between $u$ and $v$. If no path exists, distance is $\infty$.

Reachability

Vertex $v$ is reachable from $u$ if a walk exists from $u$ to $v$.

3. Traversals: Euler & Hamilton

Eulerian

Focus: Edges
  • Trail: Visit every edge exactly once.
  • Tour: Closed trail (start = end).
  • Graph: Has an Eulerian Tour.
  • Condition: Connected + All vertices even degree.

Hamiltonian

Focus: Vertices
  • Cycle: Visit every vertex exactly once.
  • Graph: Has a Hamiltonian cycle.
  • Condition: Hard to determine (NP-Complete).

4. Graph Measures

u x y w v
Definitions

Eccentricity $ecc(v)$: Max dist from $v$.

Diameter: Max eccentricity (Longest shortest path).

Radius: Min eccentricity.

Central Vertex: Vertex where $ecc(v) = Radius$.

5. Graph Isomorphism

Two graphs are isomorphic if they are structurally identical—only the labels differ. There exists a bijection $V_G \to V_H$ preserving adjacency.

1 2 3 4

Graph G

$\cong$
s t u v

Graph H

Final Quiz 🧠

Test your connectivity knowledge.

1. A trail is a walk with:

2. The Girth of an acyclic graph is:

3. An Eulerian graph must have:

4. The distance $d(u,v)$ between disconnected vertices is:

5. Two graphs are isomorphic if: