Walk

A walk in a graph is a sequence of vertices where consecutive vertices are adjacent. The existence of a walk between two vertices means that it is possible to travel between them.

Let \(G = (V, E)\) be a directed graph. The sequence \((v_1, v_2, v_3, ..., v_n)\) is a walk if and only if \((v_i, v_{i+1}) \in E\) for \(1 \leq i \leq n - 1.\)
⚠ If the first and last vertices are the same \((v_1 = v_n)\), the walk is said to be closed. Otherwise, it's open.

Also, a walk may be defined as an alternating sequence of vertices and edges, where each edge connects the two vertices that appear before and after it in the sequence:

Let \(G = (V, E)\) be a directed graph. The sequence \((v_1, (v_1, v_2), v_2, (v_2, v_3), v_3, ..., v_{n-1}, (v_{n-1}, v_n), v_n)\) is a walk if and only if \((v_i, v_{i+1}) \in E\) for \(1 \leq i \leq n - 1.\)

The length of a walk is the number of edges in it. This will always be exactly \(1\) less than the number of vertices in the walk.

If a walk does not exist between at least two vertices in a graph, that graph is disconnected. A bunch of isolated components is still one graph, called a disconnected graph. On the other hand, if walks exist between every pair of vertices in a graph, that graph is connected.

In undirected graphs, if a walk exists, it can be traversed forward or backward. Simply put, a walk in an undirected graph is still a walk even if the sequence of vertices is reversed.

Contents

Path

A path is a walk where vertices are not repeated. In other words, every vertex in the walk is distinct. \((1, 2, 3)\) is a path.

If even one vertex is repeated in a walk, it cannot be a path.

Every path is a trail, but not every trail is a path. Why? A path is unable to repeat vertices, which directly implies it is unable to repeat edges. Trails are not necessarily paths though, because it's possible to not repeat edges but still repeat vertices.

Trail

A trail is a walk where edges are not repeated. In other words, every edge in the walk is distinct. \((1, 2, 3, 4, 2)\) is a trail.

If even one edge is repeated in a walk, it cannot be a trail.

Circuit

A circuit is a closed walk where edges are not repeated. It is a closed trail. \((1, 2, 3, 4, 1, 3, 1)\) is a circuit. Here's a nice algorithm for finding circuits in a graph whose vertices all have even degree: 

algorithm find_circuit is
    input: a graph G = (V, E) whose vertices all have even degree
    output: a circuit (a sequence of edges)

    let v be any vertex that is not isolated
    let trail be an empty sequence
    while there exists an edge (v, w) not in trail
        append (v, w) to trail
        v ← w
    return trail

This algorithm gradually builds up an open trail and ends as soon as it becomes a closed trail.

Cycle

A cycle is a closed walk where edges and vertices are not repeated, except for the one vertex that gets cycled back to. In other words, the only vertices that get repeated are the first and last. Cycles are special circuits. \((1, 2, 3, 4, 1)\) is a cycle.

Without introducing parallel edges or self-loops, cycles always consist of at least \(3\) vertices.

Graphs without any cycles (such as trees) are acyclic.

Logic & Proofs
Integer • Rational number • Inequality • Real number • Theorem • Proof • Statement • Proof by exhaustion • Universal generalization • Counterexample • Existence proof • Existential instantiation • Axiom • Logic • Truth • Proposition • Compound proposition • Logical operation • Logical equivalence • Tautology • Contradiction • Logic law • Predicate • Domain • Quantifier • Argument • Rule of inference • Logical proof • Direct proof • Proof by contrapositive • Irrational number • Proof by contradiction • Proof by cases • Summation • Disjunctive normal form
Set Theory
Set • Element • Empty set • Universal set • Subset • Power set • Cartesian product • String • Binary string • Empty string • Set operation • Set identity • Set proof
Functions
Function • Floor function • Ceiling function • Inverse function
Algorithms
Algorithm • Pseudocode • Command • Asymptotic notation • Time complexity • Atomic operation • Brute-force algorithm
Relations
Relation • Reflexive relation • Symmetric relation • Transitive relation • Relation composition • Equivalence relation • Equivalence class
Number Theory
Integer division • Linear combination • Division algorithm • Modular arithmetic • Prime factorization • Greatest common divisor • Least common multiple • Primality test • Factoring algorithm • Euclid's theorem • Prime number theorem • Euclidean algorithm
Induction
Proof by induction • Fibonacci sequence • Proof by strong induction • Well-ordering principle • Sequence • Factorial • Recursive definition
Combinatorics
Rule of product • Rule of sum • Bijection rule • Permutation • Combination • Complement rule • Experiment • Outcome • Sample space • Event • Probability • Probability distribution • Uniform distribution • Multiset • Sixfold way • Inclusion-exclusion principle • Pigeonhole principle
Graph Theory
Graph • Walk • Subgraph • Regular graph • Complete graph • Empty graph • Cycle graph • Hypercube graph • Bipartite graph • Component • Eulerian circuit • Eulerian trail • Hamiltonian cycle • Hamiltonian path • Tree • Huffman tree • Substring • Forest • Path graph • Star • Spanning tree • Weighted graph • Minimum spanning tree • Greedy algorithm • Prim's algorithm
Recursion
Recursion • Recursive algorithm • Correctness proof • Divide-and-conquer algorithm • Sorting algorithm • Merge sort