Path in a graph

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

Any walk between distinct endpoints contains a simple path between those endpoints, obtained by removing segments between repeated vertices.

An even-length graph path in an edge coloring is repetitively colored when its first half and second half have the same color sequence in the same order. For a path with distinct edges colored independently and uniformly from $k$ colors, the probability of a repetition on $2r$ edges is $k^{-r}$: after the first $r$ colors, the last $r$ colors are prescribed. Reversing the path preserves this property, so the corresponding bad events may be indexed by unoriented paths.

For a finite graph of maximum degree $\Delta \ge 1$, a random independent edge coloring and the Lovász local lemma prove existence of a coloring with no repetitively colored four-edge path when $k\ge 8{\Delta }^{3/2}$, and no repetitively colored six-edge path when $k\ge 5{\Delta }^{5/3}$.

A fixed edge lies in at most $\ell {\Delta }^{\ell -1}$ unoriented paths of length $\ell$. Hence a four-edge event has a closed dependency neighbourhood of size at most $16{\Delta }^3$ and probability $k^{-2}$; the symmetric local-lemma product is at most $16e{\Delta }^3/k^2$. The corresponding six-edge quantities are $36{\Delta }^5$, $k^{-3}$ and $36e{\Delta }^5/k^3$. The stated constants make both products less than one.

Both lengths can be excluded simultaneously with $k\ge C{\Delta }^{5/3}$ for an absolute constant $C$. Apply the asymmetric Lovász local lemma with parameters $x_4=2/k^2$, $x_6=2/k^3$. A path of length $\ell \in \{4,6\}$ meets at most $4\ell {\Delta }^3$ four-edge paths and $6\ell {\Delta }^5$ six-edge paths. The sums of neighbour parameters are therefore bounded by constants times $C^{-2}{\Delta }^{-1/3}+C^{-3}$. Choosing $C$ sufficiently large makes both products in the local-lemma inequalities at least one half, establishing the claim.

Find a graph path whose least edge weight is as large as possible. In a connected undirected graph, use the unique route in a maximum spanning tree. Deleting a least-weight edge on that route gives a separating cut of a graph; a heavier crossing edge would improve the tree's total weight, so every competing route contains an edge no heavier than the deleted one. This proves the bottleneck optimum without assuming distinct weights.

A longest path maximizes path length, either the number of edges or the sum of specified edge weights, under the stated endpoints and simple-path convention. In a general graph, imposing vertex simplicity makes the optimization computationally difficult; a Directed acyclic graph admits a direct dynamic programming solution. Allowing arbitrary walks instead requires care with reachable positive cycles. The convention permitting a zero-edge path gives a possible value zero even when all nonempty paths have negative weight.

Process vertices in a topological sorting, initializing a fixed source to zero and all other labels to $-\infty$. All possible predecessors have already been processed when a vertex is reached, so maximum-relaxation computes the best path ending there. Induction along the order proves correctness for arbitrary signed weights. Initializing every vertex to zero instead allows a path to start anywhere. Each vertex and edge is processed a constant number of times, giving $O(|V|+|E|)$ running time. For a nonempty-path requirement, maximize the edge-extension candidates rather than including zero as the final answer.

The weighted length of a graph path is the sum of its edge weights. With positive weights, removing a closed excursion from a walk strictly decreases its length. Hence a shortest walk between two vertices is a graph path, and minimizing weighted length is the shortest path problem.

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.

A closed walk can revisit other vertices and need not contain a simple cycle with every property of the whole closed walk, such as using both of two edge colours.

A unicyclic graph is a connected graph with exactly one graph cycle. Deleting the edges of that graph cycle leaves trees, each meeting it in exactly one vertex. Otherwise a surviving graph cycle, or a graph path between two vertices of the original graph cycle, would give another graph cycle. Thus a finite unicyclic graph is a cycle graph with rooted trees attached at its vertices.

An induced cycle is a cycle in a graph whose vertices induce exactly its cycle edges, with no edge between nonconsecutive vertices. A triangle is an induced cycle of length three. A chordal graph forbids induced cycles of length at least four.

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.

Choose $r$ distinct edges uniformly from an $n$-vertex cycle graph, with $1\le r\le n$, and delete them. Two specified vertices at oriented distance $k$ remain connected exactly when one of their two complementary edge-disjoint paths is uncut. All cuts must then lie in the other path, giving the displayed probability. The two events are disjoint because at least one edge is cut. Set $\left(\genfrac{}{}{0ex}{}{a}{r}\right)=0$ when $a<r$.

Summing the connectivity indicators for all other vertices gives an expected numberof other vertices in a tagged connected component. The sum identity follows by classifying $(r+1)$-element subsets according to their greatest element. For three cuts this is $(n-3)/2$ other vertices.

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, also called a Hamiltonian cycle, is a cycle in a graph containing every vertex of the graph. Here the convention is a finite simple graph whose edges are undirected, with $n=|V|\ge 3$. A traversal is a sequencewhere $v_0,\dots ,v_{n-1}$ are all the distinct vertices and $\{v_i,v_{i+1}\}\in E$ for $0\le i<n$. Thus "once" means once before the closing return: the start appears again at the end, and there are exactly $n$ traversed edges. The graph may contain additional unused edges.^[ref]

A Hamiltonian path visits all vertices once without requiring a return. Removing an edge from a Hamilton cycle gives a Hamiltonian path; a particular Hamiltonian path closes only if its endpoints are adjacent. An Euler circuit instead traverses every edge exactly once and can revisit vertices midway. The two requirements are independent, as these original labelled examples show.

For the complete graph $K_4$, use $V=\{A,B,C,D\}$ and $E=\{AB,AC,AD,BC,BD,CD\}$, where $AB$ abbreviates the unordered pair $\{A,B\}$. The route $A,B,C,D,A$ is a Hamilton cycle: it visits every vertex and uses four of the six edges, omitting $AC$ and $BD$. It is not an Euler circuit, and the graph admits no Euler circuit at all: every vertex degree is three, contradicting the Euler circuit criterion. The crossing of the drawn diagonals is not another vertex.

Conversely, take two triangles in a graph sharing only $X$, with $V=\{X,A,B,C,D\}$ and $E=\{XA,AB,BX,XC,CD,DX\}$. The route $X,A,B,X,C,D,X$ is an Euler circuit, using all six edges once; the vertex degrees are $4,2,2,2,2$. It cannot be a Hamilton cycle, since $X$ occurs midway as well as at the start and end. More strongly, no Hamilton cycle exists: $X$ is a cut vertex, and deleting it leaves the two separate edges $AB$ and $CD$. Nevertheless, $A,B,X,C,D$ is a Hamiltonian path, whose endpoints are not adjacent.

A Hamiltonian graph is a graph containing a Hamilton cycle. This describes existence of a spanning graph cycle, rather than requiring every edge of the graph to belong to that graph cycle. In the finite simple graph convention, $K_n$ is a Hamiltonian graph for $n\ge 3$, because any ordering of its vertices closes using available edges.

Ore's theorem, named after Øystein Ore, says that a finite simple graph with $n\ge 3$ vertices is Hamiltonian if every nonadjacent pair has degree sum at least $n$.

For a proof, enlarge a hypothetical counterexample to an edge-maximal non-Hamiltonian graph. Adding a missing edge $uv$ creates a Hamiltonian cycle, hence the original graph has a Hamiltonian path $u=v_1,\dots ,v_n=v$. If both $u{v}_{i+1}$ and $v{v}_i$ are edges, the path closes to a cycle by reversing its final segment. Thus the index sets of these two kinds of edges are disjoint in $\{1,\dots ,n-1\}$, giving $d(u)+d(v)\le n-1$, a contradiction. The degree condition is sufficient and need not follow from a lower bound of $n/2$ on every individual degree.

A Hamiltonian graph must be a connected graph and have minimum degree $\delta (G)\ge 2$: each vertex has two distinct neighbours on its Hamilton cycle. It also has no cut vertex. Indeed, deleting any vertex from the Hamilton cycle leaves a graph path through every remaining vertex, so the remaining graph is connected. These are quick ways to rule out a Hamilton cycle.^[ref]

Even these conditions together are not sufficient: the complete bipartite graph $K_{2,3}$ is connected, has minimum degree two and no cut vertex, but has no Hamilton cycle. Every graph cycle in a bipartite graph alternates between its two parts, using equally many vertices from each; it cannot use all two and all three.

In the other direction, Dirac's theorem gives a sufficient condition: a finite simple graph with $n\ge 3$ and $\delta (G)\ge n/2$ has a Hamilton cycle. Failure of this inequality proves nothing by itself: the cycle graph $C_5$ has a Hamilton cycle despite $\delta (C_5)=2<5/2$.^[ref]

A weighted Hamilton cycle is a Hamilton cycle in a weighted graph, with cost equal to the sum of its traversed edge weights. Here weights represent symmetric nonnegative costs, rather than conductances. Asking whether a Hamilton cycle exists is a feasibility question; asking for the cheapest one is an instance of the travelling salesman problem. A complete graph supplies every possible connection between distinct vertices, making feasibility automatic for $n\ge 3$, while choosing the cheapest visiting order remains a separate mathematical optimization problem.

Assign the complete graph $K_4$ the symmetric edge costs $w_{AB}=2$, $w_{BC}=3$, $w_{CD}=4$, $w_{AD}=5$, $w_{AC}=6$ and $w_{BD}=7$, in arbitrary units. Fix the start at $A$ and identify each Hamilton cycle with its reverse. The three possibilities areThese exhaust the possibilities: the permutations of the other three vertices give $3!=6$ orders, paired into three reversals. Hence the perimeter tour really is optimal for this toy instance. The diagram's geometric lengths are not costs, and no triangle inequality is assumed.

The usefulness of this model is to distinguish visiting required sites from covering required connections. If tasks are assigned to vertices and the route must return after one visit to each, a weighted Hamilton cycle captures the ordering requirement. If the job instead requires each edge once, the relevant object is an Euler circuit. The shortest path problem asks only for a cheapest route between specified endpoints. A 1954 primary research paper gave a concrete motivation for the travelling salesman problem: certify that a particular tour through 49 cities has minimum road-distance cost.^[ref]

These are abstract route models. If a cost stands for a whole graph path through an underlying network, travelling between consecutive task vertices can pass through intermediate network vertices more than once. One visit per task therefore does not imply one visit per physical junction. One-way connections require a directed graph; changing costs or extra timing constraints require a richer model than the fixed symmetric toy instance.

The Icosian game made the vertex-visit puzzle tangible. The report of its 1857 presentation describes a plane projection of a regular dodecahedron, with holes at the vertices for ivory pins. The Trinity College Dublin archive connects this game with the search for closed routes visiting each vertex exactly once. This puzzle supplies a historical illustration of the Hamilton cycle requirement.^[ref]

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.

This path-length bound is a different result from the Erdős-Gallai theorem on degree sequences.