Math 2.0

Combinatorics Definition

Path

Builds on Walk

Definition

Let GG be a graph. A path in GG is a walk (w0,w1,…,wk)(w_0, w_1, \dots, w_k) whose vertices w0,w1,…,wkw_0, w_1, \dots, w_k are pairwise distinct.

Remarks

A path uses each edge at most once, so every path is a trail. A path of length kk has k+1k + 1 vertices. Its vertices and edges form a subgraph isomorphic to the path graph Pk+1P_{k+1}. Each walk from uu to vv contains a path from uu to vv. The node every walk contains a path states this.

Reading path

To understand this page from the ground up, read these 3 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 levelPathdefinition
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

Where this leads

7 pages build on this one.

Further reading

  1. Web https://en.wikipedia.org/wiki/Path_(graph_theory), Walk, trail, and path
About this page
Tag0JDE56HWQ8
URIm2://0JDE56HWQ8
Kinddefinition
WritingW1 stated
MSC05C38
DefinesPath
UsesWalk

Markdown · JSON · Edit on GitHub

What this page needs for W2

  • edge instance_of in: one example (0 of 1)
  • edge not_instance_of in: one non-example that fails one clause (0 of 1)

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

What links here

Used by

Results about this