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

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!

I hope you find this video helpful, and be sure to ask any questions down in the comments!

********************************************************************
The outro music is by a favorite musician of mine named Vallow, who, upon my request, kindly gave me permission to use his music in my outros. I usually put my own music in the outros, but I love Vallow's music, and wanted to share it with those of you watching. Please check out all of his wonderful work.

********************************************************************

+WRATH OF MATH+

Follow Wrath of Math on...

[neelabhabanerjee]

you wouldnt believe how much this graph playlist is helping me!
thanks a ton bro <3

[brajeshmohanty]

Thankyou so much sir my eyes literally filled with tears when I watched your video cause u taught the concept in a very easy method. In my university the faculty of this subject just mug up all these and split it on the board but thank you so much sir

[ashutoshsharma]

Sir, excellent explanation. I've a question that when you say that we are deleting some vertices following from u(i +1) to u(j), and because u(i) = u(j), it does implies that there are multiple loops on u(i). Are multiple loops valid on a single vertex in graph theory?.

[suthakutty]

This is one of my seminor theorem I have more doubts on it ..but now I clear my doubts through comments also..somethings I note in your vedio that is..your words are not well clear to hear me and what are you writing on the board not clear to see ...that's all...and thank you so much for your vedio ..✨✨

[chutiyadaaku]

Sir, we can also leave the proof open ended; after we delete the few vertices from the walk then we can say that
1. If no vertices are repeated in W1 then it's a path
2. If the vertices are still repeated then we can repeat the method till we get a path.

Is the second step correct? Kindly correct me if i am wrong, sir.

[gunshy]

Thank you made it easy to understand :)

[luciano]

good proof. mathematical logic is pretty cool. takes a little bit of thinking though to understand the contradiction in the proof

[PunmasterSTP]

u-v walk? More like "U rock!"