Skip to content
Tutorials Center
My learning

Topics

Lesson 10 of 36 ยท Connectivity and Paths

Walks, Paths and Cycles

Learn the difference between walks, trails, paths and cycles, what connected means, how distance, diameter and girth are defined, and compute them in Python.

A graph is only interesting when you can move around in it. This lesson defines the ways of moving: walks, trails, paths and cycles, then uses them to define connectedness, distance, diameter and girth. These words are used precisely in theorems, so it is worth learning them exactly.

Walks, trails and paths

A walk is a sequence of vertices v0, v1, ..., vk in which each consecutive pair is joined by an edge. Its length is the number of edges, k. Vertices and edges may repeat.

Stricter versions:

Name Repeated edges? Repeated vertices?
Walk allowed allowed
Trail no allowed
Path no no

Every path is a trail and every trail is a walk, but not the other way round. In the Kรถnigsberg problem you wanted a trail that uses all edges.

A walk is closed if it starts and ends at the same vertex. A cycle is a closed walk of length at least 3 (at least 2 in multigraphs) in which the only repeated vertex is the first/last one. In short, a cycle is a path whose ends are joined. A graph with no cycles is acyclic.

graph LR
  a --- b
  b --- c
  c --- d
  d --- a
  c --- e
  e --- f

a-b-c-d-a is a cycle. a-b-c-e-f is a path. a-b-c-d-a-b is a closed walk that is not a cycle.

Python Classify a walk

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Connected graphs

Two vertices are connected if some path joins them. A graph is connected if every pair of vertices is connected; otherwise it falls apart into components, maximal connected pieces (see connected components).

A useful fact: if a walk goes from u to v, then there is a path from u to v too. Whenever a vertex repeats, cut out the loop between the repeats and the walk shortens without losing its endpoints. So "there is a walk" and "there is a path" are equivalent for connectivity.

Distance, eccentricity, diameter

The distance d(u, v) is the length of a shortest path between u and v (infinite if none exists). From it:

  • The eccentricity of v is the largest distance from v to any other vertex.
  • The diameter is the largest eccentricity: the longest shortest path.
  • The radius is the smallest eccentricity, and a vertex achieving it is a center.
  • The girth is the length of the shortest cycle (infinite for acyclic graphs).

We compute distances with a breadth-first search in the next lesson. Here is a simple Floyd-Warshall style version (triple loop) that is fine for tiny graphs:

Python Distance, diameter, radius

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Counting walks and finding short cycles

Recall that powers of the adjacency matrix count walks (adjacency matrix). The smallest k for which (A^k)[i][j] > 0 is the distance from i to j. For girth we can search for the shortest cycle through each edge u-v: remove the edge, find the shortest remaining path from u to v, and add 1.

Python Girth by deleting each edge

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Key facts to remember

  • A graph on n vertices with m < n - 1 edges cannot be connected.
  • A connected graph with m = n - 1 edges is a tree and has no cycle.
  • If every vertex has degree at least 2, the graph contains a cycle (follow edges until you revisit a vertex).
  • A graph is bipartite exactly when all its cycles are even.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which is the most restrictive: a walk, a trail or a path?

    A path forbids repeated vertices (and hence repeated edges); a trail forbids only repeated edges; a walk forbids nothing.
  2. 2. What is the diameter of a graph?

    Diameter = max over all pairs of d(u, v), the farthest any two vertices are apart.
  3. 3. A graph with 10 vertices and 8 edges:

    A connected graph needs at least n - 1 = 9 edges.
  4. 4. What is the girth of an acyclic graph?

    Girth is the length of the shortest cycle; with no cycles it is conventionally infinite.

Summary

  • Walks may repeat anything; trails repeat no edge; paths repeat no vertex; cycles are closed paths.
  • A graph is connected if every pair of vertices is joined by a path.
  • Distance is the length of a shortest path; eccentricity, radius, diameter and girth derive from it.
  • Every walk between two vertices contains a path between them.
  • A graph needs at least n - 1 edges to be connected.

Next: Breadth-First Search