Guide to Walks, Trails, Paths, Circuits, and Cycles! [Graph Theory Tutorial]

This video explains walks, trails, paths, circuits, and cycles in graph theory.

In graph theory, a walk is defined as a sequence of alternating vertices and edges, like Vertex 1, Edge 1, Vertex 2, Edge 2, etc. Walks are how we traverse a network. In a walk, you are allowed to repeat edges and vertices as many times as you'd like. A trail, on the other hand, is a walk in which you do not repeat edges. And a path is a walk in which you do not repeat edges and you do not repeat vertices (note that the set of paths in a graph is a subset of trails in that graph).

I think it's important to know that some authors do define these terms slightly differently; some refer to what we just called a 'trail' as a 'path' as well, while referring to what we called a 'path' as a 'simple path' instead.

Here are some links for more information:
https://www.geeksforgeeks.org/mathema...
http://mathonline.wikidot.com/walks-t...
https://mathworld.wolfram.com/Walk.html

Recommended Books:
******************************* Hypergraph Theory *******************************
"Hypergraph Theory: An Introduction": https://amzn.to/48WKqfy

******************************* Graph Theory *******************************
"Introduction to Graph Theory (Trudeau)": https://amzn.to/48ZWhtj

"Graph Theory (Diestel)": https://amzn.to/4aYCSdW

******************************* Misc. Undergraduate Mathematics *******************************
Discrete Mathematics with Applications (Epp): https://amzn.to/4aWC1dM

A Book of Abstract Algebra (Pinter): https://amzn.to/3S2QmfV

Language, Proof and Logic: https://amzn.to/47EIZkE

Linear Algebra and Its Applications: https://amzn.to/48QsoMt

All the Math You Missed: https://amzn.to/3u5dORP

These are my Amazon Affiliate links. As an Amazon Associate I may earn commissions for purchases made through the links above.

0:00 - Graph Walks
0:53 - Graph walks as lists
1:35 - Trails
2:50 - Circuits
3:30 - Paths
4:50 - Closed paths = Cycle
5:30 - Summary
6:44 - Real-world Example
7:35 - Traveling Salesman Problem