What is a Walk? | Graph Theory

What is a walk in the context of graph theory? That is the subject of today's math lesson! A walk in a graph G can be thought of as a way of moving through G, where you start at any vertex in the graph, and then move to other vertices through the edges in the graph. In a walk, you are allowed to traverse the same vertices and edges multiple times.

So, a walk can be described as a sequence of vertices. Let's say we have the graph G and G = ( V, E ) where V = { a, b, c, d, e, f } and E = { ab, ac, de, ef, cd }. Then we could describe a walk in G like this: W = ( c, a, b, a, c, d ). So a walk is a sequence of vertices in a graph, where consecutive vertices are adjacent in that graph. Notice in the walk W, all consecutive vertices are joined by an edge, and we traversed some of the same vertices and edges multiple times.

If a walk starts and ends on the same vertex, it is called a "closed walk", otherwise it is called an "open walk". The vertices and edges encountered during the walk are said to "lie on" the walk. So going back to the walk W = ( c, a, b, a, c, d ), the vertex c lies on W, as does the edge ca. Also, we can call W a c-d walk in G, because it starts at vertex c, ends at d, and is a walk in G.

An alternative way of defining walks, which is often used instead, is for them to be a sequence of alternating vertices and edges. In this way of defining a walk, the walk starts and ends with a vertex, but after a vertex you list the edge traveled, then the vertex you are on, then the edge traveled, and so on up until the final vertex you stop at. So remember our walk W = ( c, a, b, a, c, d ). If we were to write this walk using this alternative definition, we would write W = ( c, ca, a, ab, b, ba, a, ac, c, cd, d ). This way of defining walks lets the edges traversed be much more explicit, since they are listed out right in the sequence instead of being implied by the vertices traveled. This definition is sometimes preferred, and is very common.

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

+WRATH OF MATH+

◆ Support Wrath of Math on Patreon:   / wrathofmathlessons  

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

Music Channel:    / seanemusic