Proof: If There is a u-v Walk then there is a u-v Path | Every Walk Contains a Path, Graph Theory

Описание: Support the production of this course by joining Wrath of Math to access all my graph theory videos!
   / @wrathofmath  
🛍 Check out my math fashion brand! https://mathshion.com/

Graph Theory course:    • Graph Theory  
Graph Theory exercises:    • Graph Theory Exercises  

Get the textbook! https://amzn.to/3HvI535

PLEASE NOTE: The condition that u is not equal to v is not technically necessary, because the path described by the sequence ( u ) is considered a u-u path of length 0. If we allow this to be a path, the proof we go over covers this possibility with no changes necessary, and so the theorem is proved for all walks, regardless of whether u and v are equal or not.

If there is a u-v walk of length n in a graph, then there is a u-v path of length at most n, provided that u is not equal to v. We will prove this simple but useful result in today's video graph theory lesson!

It should seem fairly self-evident that the existence of a walk between two vertices implies the existence of a path between those vertices that is at most as long as the walk. If a walk is not a path, then it must repeat vertices, the vertices visited between the duplicate vertices can be deleted, leaving a shorter walk behind. If this process is repeated as much as possible, a path will be created.

If we know a u-v walk exists, we can take a shortest u-v walk. Then we use proof by contradiction and show this shortest walk, if it is not a path, can be shortened, producing a contradiction and proving the shortest walk must be a path.

If you're taking a course in Graph Theory, or preparing to, you may be interested in the textbook that introduced me to Graph Theory: “A First Course in Graph Theory“ by Gary Chartrand and Ping Zhang. It’s a wonderful text! You can purchase this book through my Amazon affiliate link below! Using the affiliate link costs you nothing extra, and helps me continue to work on Wrath of Math!

◆ Support Wrath of Math on Patreon:   / wrathofmathlessons  

Follow Wrath of Math on...
● Instagram:   / wrathofmathedu  
● Facebook:   / wrathofmath  
● Twitter:   / wrathofmathedu