Graph theory · Definition

Path in a graph

discrete mathematicsgraphs

Before you start you need to know

It formalises going from one vertex to another along edges, the basis of connectedness and distances.

Definition

A path of length \(k\) is a sequence of vertices \(v_0,\dots,v_k\) such that each consecutive pair is joined by an edge of \(E\).

\[\{v_{i-1},v_i\}\in E,\qquad i=1,\dots,k\]

The length of a path is the number of edges it uses, one fewer than the number of vertices listed. A single vertex is a path of length \(0\). If vertices and edges may repeat the sequence is called a walk; if no vertex repeats, a simple path. Several textbooks use «path» for the general walk and «simple path» for the one with no repeated vertex.

Since edges have no direction, traversing a path backwards gives another path: if one can go from \(u\) to \(v\), one can go from \(v\) to \(u\). This symmetry is what lets us split the vertices into separate pieces when studying connectedness.

Paths are counted with the adjacency matrix \(A\): the \((i,j)\) entry of \(A^k\) is the number of walks of length \(k\) from \(i\) to \(j\). That is why the diagonal of \(A^2\) holds the degrees. The distance between two vertices is the length of the shortest path joining them, found by exploring the graph level by level.

A typical mistake is confusing length with the number of vertices, or assuming the shortest path is unique. Paths are the tool used to define connectedness and, when they return to their starting point, cycles.

Think about it

How many vertices does a simple path of length 7 have?

It has 8 vertices: one more than the edges, all distinct.

Exercises 10

  1. What is the length of the path \(1,2,3,4\) in a graph where \(12\), \(23\) and \(34\) are edges?
  2. A graph has edges \(12, 23, 34, 14, 25\). Which of these sequences is a path?
  3. In the 5-cycle \(1,2,3,4,5\) (edges \(12,23,34,45,51\)), what is the length of the shortest path from \(1\) to \(3\)?
  4. A graph has edges \(12, 13, 23, 34\). How many walks of length 2 (vertices may repeat) start and end at \(3\)?
  5. A path passes through 5 distinct vertices. What is its length?
  6. Take the graph with edges \(12, 23, 34\). How many walks of length 3 go from \(1\) to \(2\) (vertices may repeat)?
  7. What is the maximum length of a path with no repeated vertices in the complete graph \(K_6\)?
  8. If a graph has a path from u to v, what can be guaranteed?
  9. A graph has edges \(12, 23, 34, 45, 16, 65, 25\). What is the distance (length of a shortest path) between \(1\) and \(4\)?
  10. How many paths with no repeated vertices go from \(1\) to \(4\) in the complete graph \(K_4\)?

References

  • Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th edition, McGraw-Hill, 2019. §10.4
  • Susanna S. Epp, Discrete Mathematics with Applications, 5th edition, Cengage, 2019. §10.2
  • Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, 5th edition, Pearson, 2003. §11.2