# Walk and Path - Graph Theory - Discrete Mathematics | Summary and Q&A

4.5K views
April 8, 2022
by
Ekeeda
Walk and Path - Graph Theory - Discrete Mathematics

## TL;DR

A walk is a sequence of vertices and edges in a graph where edges are visited once, while a path is a type of walk where both edges and vertices are not repeated.

## Key Insights

• 🦔 Walks in graph theory are finite sequences of vertices and edges, with a restriction on the repetition of edges, but not on vertices.
• ❤️‍🩹 An open walk has different starting and ending vertices, while a closed walk has the same starting and ending vertex.
• 🚶 A path is a specific type of walk that is also an open walk, with no repeated edges or vertices.
• 🦔 In a path, both edges and vertices must not be visited more than once.
• 👻 The distinction between walks and paths allows for more precise analysis of graph structures.
• 🌍 Graph theory concepts can be applied to various real-world scenarios, such as network routing or social network analysis.
• 🚶 The understanding of walks and paths is fundamental for further exploration of graph theory and its applications.

### Q: What is a walk in graph theory?

A walk in graph theory refers to a finite sequence of vertices and edges in a graph, where each edge is incident with the vertices preceding and following it. The edges must not be visited more than once, but there is no restriction on the vertices.

### Q: What is the difference between an open walk and a closed walk?

An open walk is a type of walk where the starting and ending vertices are different. On the other hand, a closed walk has the same starting and ending vertex.

### Q: What is a path in graph theory?

A path is a type of walk in graph theory that is both an open walk and where both edges and vertices are not repeated. It is a sequence of vertices and edges that starts and ends with different vertices, and no vertex or edge is visited more than once.

### Q: Can a walk have repeated vertices but non-repeated edges?

Yes, a walk in graph theory can have repeated vertices as long as the edges are not repeated. The restriction is on the edges, not the vertices.

## Summary & Key Takeaways

• A walk is a sequence of vertices and edges in a graph where edges are visited once, while vertices can be repeated.

• An open walk is a walk where the starting and ending vertices are different, while a closed walk has the same starting and ending vertex.

• A path is a type of walk that is also an open walk, where both edges and vertices are not repeated.