Math 2.0

Combinatorics Proposition

Every walk contains a path

Builds on WalkPath

Statement

Let GG be a graph and let u,vu, v be vertices of GG. Suppose that there is a walk WW from uu to vv. Then there is a path from uu to vv whose vertices and edges are vertices and edges of WW.

Remarks

Proof idea: if a walk visits a vertex xx twice, delete the closed part between the two visits. Each deletion makes the walk shorter, so the process stops with a path. A consequence: a shortest walk from uu to vv is a path. Thus the distance can be defined with paths.

Reading path

To understand this page from the ground up, read these 4 pages in order. The foundations come first.

Show the path as a graph
Graph, definition, no evidence levelGraphdefinitionWalk, definition, no evidence levelWalkdefinitionPath, definition, no evidence levelPathdefinitionEvery walk contains a path, statement, no evidence levelEvery walk contains a…statement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Graph definition
  2. Walk definition
  3. Path definition
  4. Every walk contains a path statement

Further reading

  1. Web https://en.wikipedia.org/wiki/Path_(graph_theory), Walk, trail, and path
About this page
Tag09VZBHB33V
URIm2://09VZBHB33V
Kindstatement, proposition
WritingW0 stub
MSC05C38
StatusThis copy of the site has no build data. Run m2 status 09VZBHB33V.
UsesWalk, Path

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.