Path in a graph

A path of length $t$ is a sequence of $t+1$ distinct vertices in which consecutive vertices are adjacent.

A Hamiltonian path is a path in a graph that visits every graph vertex exactly once. Removing any edge from a Hamilton cycle produces a Hamiltonian path. Conversely, a Hamiltonian path closes to a Hamilton cycle exactly when its endpoints are joined by an edge.

Paths are edge-disjoint when no graph edge occurs in two of them. They may share internal vertices. If $r$ edge-disjoint client-to-server paths exist, fewer than $r$ failed links cannot destroy them all. For simultaneous link and node failures one instead needs internally vertex-disjoint paths, since one shared internal node could destroy several edge-disjoint paths at once.

A graph ray is an infinite sequence $v_0,v_1,\dots$ of distinct graph vertices with an edge between consecutive graph vertices. Every infinite connected locally finite graph contains a graph ray from each graph vertex, by the König infinity lemma applied to its finite self-avoiding graph paths. An open graph ray witnesses an infinite percolation cluster.

A path graph $P_n$ has $n$ vertices in a single chain and $n-1$ edges. Its endpoint graph distance is $n-1$ and, with unit resistances, its endpoint effective resistance is also $n-1$.

A cycle is a closed path: its final vertex is joined back to its initial vertex, and no other vertex is repeated.

The girth of a graph containing a cycle is the length of its shortest cycle. A forest is conventionally assigned infinite girth.

An odd cycle is a cycle in a graph with an odd number of edges.

The cycle graph $C_n$ has vertices $v_1,\dots ,v_n$ and edges $v_i{v}_{i+1}$, with indices read cyclically.

A wheel graph is the join of graphs of a cycle graph and a single vertex. Every wheel with a rim of at least three vertices has a $K_4$ graph minor: partition the rim into three nonempty consecutive connected sets and use its centre as the fourth branch set of a graph minor.

A Hamilton cycle is a cycle containing every vertex of its graph.

An $n$-vertex graph is pancyclic when it contains $C_{\ell }$ for every $3\le \ell \le n$.

Every connected $n$-vertex graph of minimum degree $\delta$ contains a path of length at least $\min (2\delta ,n-1)$.

An $n$-vertex graph containing no path of length $t$ has at most $(t-1)n/2$ edges.