◀ ▲ ▶Branches / Graph-theory / Definition: Closed Walks, Closed Trails, and Cycles

Definition: Closed Walks, Closed Trails, and Cycles

Let \(G(V,E,\gamma)\) be a simple graph. * A walk (or trail) \(W^k=v_0e_0v_1e_1v_2e_2\ldots e_{k-1}x_{k}\) in \(G\) is called a closed walk (or a closed trail) if \(x_k=x_0\). * A path \(C^k:=x_0x_1\ldots x_{k-1}x_k\) with \(x_0=x_k\), but \(x_0\neq x_i\) for \(i=1,\ldots,k-1\) is called a cycle. Note that from this definition it allows any cycle in a simple graph contains at least three different vertices. * An edge which joins two vertices of a cycle but is not itself an edge of the cycle is a chord of that cycle.

Examples:

In the figure above:

• \(abcgfcdefcdefgha\) is a closed walk, but not a closed trail because the e.g. the edges \(gf\), \(cd\), etc. are passed more then once.
• \(abcdefcgha\) is a closed trail, but not a cycle because the vertex \(c\) is passed more then once.
• \(abcdefgha\) is a cycle (every edge and every vertex is passed exactly once); the edges \(cg\) and \(cf\) are the chords of that cycle.
• \(abcgha\) is a cycle without any chords.

Table of Contents

1. Definition: Girth and Circumference
2. Definition: Cyclic, Acyclic Graph

Mentioned in:

Definitions: 1 2 3 4 5 6 7 8 9 10
Explanations: 11
Lemmas: 12
Proofs: 13 14 15 16 17 18 19 20 21
Propositions: 22 23 24
Theorems: 25 26 27

Thank you to the contributors under CC BY-SA 4.0!

Github:

References

Bibliography

1. Aldous Joan M., Wilson Robin J.: "Graphs and Applications - An Introductory Approach", Springer, 2000
2. Diestel, Reinhard: "Graph Theory, 3rd Edition", Springer, 2005