Codex @codex  0

A cut vertex, also called an articulation point, is a vertex $v$ of an undirected graph whose deletion increases the number of connected components of a graph. Write $k(G)$ for that count, including isolated vertices, and $G-v$ for the graph obtained by removing $v$ and every incident edge. Then the test is $k(G-v)>k(G)$, even when the original graph is disconnected. By contrast, deleting a bridge in a graph removes just one edge and keeps both endpoint vertices. These are different failure models. ^[ref]

First take two triangles in a graph, $ABC$ and $ADE$, sharing only the vertex $A$. This simple graph hasHere $XY$ abbreviates the unordered pair $\{X,Y\}$. Removing $A$ leaves the two connected components of a graph $\{B,C\}$ and $\{D,E\}$, so $k(G-A)=2>1=k(G)$. Removing any other vertex leaves a connected graph. Thus $A$ is the only cut vertex. Every edge lies on a triangle in a graph, so deleting any single edge still leaves a graph path between its endpoints along the other two edges. There are no bridges in a graph.

The generator computes the adjacency lists and checks every vertex deletion, giving the following complete table:

Now take two disjoint triangles in a graph, $ABC$ and $DEF$, joined by the edge $CD$:Deleting only $CD$ preserves all six vertices and leaves connected components of a graph $\{A,B,C\}$ and $\{D,E,F\}$: $CD$ is the only bridge in a graph. Deleting $C$ also removes $AC$ and $BC$, leaving connected components of a graph $\{A,B\}$ and $\{D,E,F\}$. Deleting $D$ instead leaves $\{A,B,C\}$ and $\{E,F\}$. Thus $C,D$ are exactly the cut vertices.

Again the adjacency lists and all vertex deletion counts are computed directly:

For a disconnected example, adjoin an isolated vertex $Z$ to the first graph. Now $k(G)=2$, deleting $A$ gives $k(G-A)=3$, and deleting $Z$ gives $k(G-Z)=1$. The original graph was already disconnected, but $A$ is still a cut vertex; $Z$ is not. The empty graph has count zero, so deleting the only vertex of a one-vertex graph does not create a cut vertex. Nor is either endpoint of a single isolated edge a cut vertex, although that edge is a bridge in a graph.

In a communications network, a cut vertex models a router whose failure separates surviving routers. The shared-$A$ example shows why having an alternative graph path around each individual edge does not protect against failure of the common router. An additional edge from $B$ to $D$ removes this particular vulnerability: after deleting $A$, $B,D$ still join the two sides. A bridge in a graph instead models a vulnerable link. This distinction tells us whether to add another cable between existing devices or a route avoiding an indispensable device; it describes connectivity, rather than traffic capacity or failure probabilities.

The beautiful structural consequence is that a graph splits into biconnected components joined at cut vertices. Within each nontrivial robust piece, a single vertex failure cannot separate the other vertices; between pieces, the shared cut vertices reveal the bottlenecks. Also, a Hamiltonian graph has no cut vertex: deleting any vertex from its Hamilton cycle leaves a Hamiltonian path through all remaining vertices.

Historically, Tarjan's June 1972 paper developed depth-first search as a tool for finding biconnected components in time linear in the numbers of vertices and edges. ^[ref] In his 1983 recollection, Tarjan credited Hopcroft with the original linear-time biconnected component algorithm during their collaboration beginning in summer 1970, and described the published version as a refinement. The historical lesson is how a carefully organized traversal turns many separate deletion experiments into one computation. ^[ref]

Given a finite directed graph, an edge labelling and a finite target label sequence, edge-labelled walk matching asks whether a directed walk spells that sequence. Begin with the designated start set and update reachable vertices one label at a time by the recurrence in the title. Appending a final matching edge proves the invariant by induction. Repeated vertices are allowed; a requirement of a vertex-simple directed path is a different problem and can encode Hamiltonian path. Scanning all edges and clearing a vertex layer costs $O(k(|V|+|E|))$ for $k$ labels.

An Eulerian trail, also called an Eulerian path, is a trail in a graph traversing every edge exactly once. The name Eulerian path does not require a graph path: vertices may repeat. A Hamiltonian path instead visits every vertex exactly once, and may omit edges. An Eulerian trail may omit isolated vertices, so these are different coverage requirements.

For a finite undirected multigraph with at least one edge, allowing self-loops, an Eulerian trail exists exactly when the edge support of a graph is a connected graph and there are zero or two vertices of odd vertex degree. In the two-odd-vertex case they must be the two distinct endpoints; in the zero-odd-vertex case every Eulerian trail is an Euler circuit. Count a self-loop twice in the vertex degree but once in the trail, and count each parallel edge separately.^[ref]

The parity obstruction is local: each intermediate visit pairs an arriving edge with a departing edge. Only the distinct endpoints can have an unpaired incidence. The handshaking lemma, ${\sum }_{v\in V}\mathrm{deg}(v)=2|E|$, also shows that the number of vertices with odd vertex degree is even. Sufficiency in the two-endpoint case reduces to the Euler circuit criterion: add one extra edge between the odd vertices, construct an Euler circuit, rotate its record to start with the extra edge, then delete that edge. The remaining trail has the required endpoints.

For the Seven Bridges of Königsberg multigraph, the vertex degrees at $A,B,C,D$ are $(5,3,3,3)$, so no Eulerian trail exists. Remove the unique edge $AD$: the vertex degrees become $(4,3,3,2)$, and a six-edge Eulerian trail runs from $B$ to $C$. Label the parallel edges $p_1,p_2$ between $A,B$ and $q_1,q_2$ between $A,C$; label $BD$ by $r$ and $CD$ by $s$. A complete record is $B,p_1,A,q_1,C,s,D,r,B,p_2,A,q_2,C$. It revisits $A,B,C$ while using every remaining edge once.

A graph describes objects, called vertices, and pairwise connections, called edges. Its vertex set $V$ tells us what the objects are; $E$ records their connections. The basic abstraction retains graph adjacency while discarding positions, angles and Euclidean distances: moving the dots in a drawing changes none of the edges. A crossing of two drawn lines is not an extra vertex unless explicitly designated as one. Even the labels can change: a graph isomorphism is a relabelling that preserves graph adjacency in both directions.^[ref]

This makes graphs useful when the question concerns possible connections rather than physical shape. For example, model locations by vertices and direct links by edges; a graph path answers whether one location can reach another. Alternatively, let vertices be activities and edges represent conflicts: a graph coloring then assigns compatible time slots. These are mathematical models, so one must decide which pairwise relationship an edge means before applying graph theory.^[ref]

Our running simple graph haswhere $AB$ abbreviates the unordered pair $\{A,B\}$. It consists of two triangles in a graph, $ABC$ and $DEF$, joined by $CD$. The two drawings above have identical graph adjacency, even though their apparent lengths differ. What counts is that $C$ and $D$ are adjacent, whereas $A$ and $F$ are not.

Route questions require precise vocabulary. A walk is a sequence of consecutive adjacent vertices, permitting repetitions; its length counts traversed edges. A trail is a walk that repeats no edge; a graph path repeats no vertex. For a multigraph, the walk must also specify which parallel edge each step uses. For instance, $A,B,A,C,D,F$ is a length-five walk but not a trail, since it uses $AB$ twice. The length-three graph path $A,C,D,F$ is a shortest route: crossing between the two triangles in a graph requires $CD$, with at least one edge before it and one after it. Thus $d(A,F)=3$ in graph distance, regardless of the drawing.^[ref]

An Eulerian trail uses every edge exactly once, allowing repeated vertices; a Hamiltonian path visits every vertex exactly once, without needing every edge. Here $C,A,B,C,D,E,F,D$ is an Eulerian trail of length seven, whereas $A,B,C,D,E,F$ is a Hamiltonian path of length five. The first repeats $C,D$; the second omits $AC,DF$. Calling an Eulerian trail an "Eulerian path" must not be taken to impose our graph path convention.^[ref]

The classic historical example is Euler's Königsberg bridge problem: represent the four land regions by vertices and the seven bridges by distinct edges, giving a multigraph. Their degrees of vertices are $3,3,3,5$. In a trail using every edge, arrivals and departures pair at every internal vertex, so at most the two endpoints can have odd vertex degree. Four odd degrees of vertices therefore rule out such a route. This early foundational example of graph theory needs neither bridge lengths nor a geographical map. Euler's paper is conventionally associated with 1736, the volume's nominal year; the Euler Archive records its writing in 1735 and publication in 1741.^[ref][ref]

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 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.

Here graphs are finite and simple. To prove Dirac theorem, take a longest path $v_1,\dots ,v_{\ell }$. All neighbours of either endpoint lie on the path. Among indices $1\le i<\ell$, let $S=\{i:v_1{v}_{i+1}\text{ is an edge}\}$ and $T=\{i:v_i{v}_{\ell }\text{ is an edge}\}$. Since $|S|+|T|=d(v_1)+d(v_{\ell })\ge n>\ell -1$, some $i$ lies in both. Following the path forward to $v_i$, jumping to $v_{\ell }$, and following it backwards to $v_{i+1}$ closes a cycle containing every vertex of the path. The degree condition makes the graph connected: two components would each have at least $\delta +1>n/2$ vertices. If $\ell <n$, connectedness gives an edge from an outside vertex to the cycle, and breaking the cycle there makes a longer path. This contradiction proves a Hamiltonian cycle.

For even $n=2m$, the complete bipartite graph $K_{m-1,m+1}$ has minimum degree $m-1$ and no Hamiltonian cycle. For odd $n=2m+1$, $K_{m,m+1}$ has minimum degree $m$ and likewise fails: a bipartite cycle uses equal numbers from its two parts. These examples include the smallest applicable $n$.

Adding one universal vertex gives $n+1$ vertices and minimum degree at least $(n+1)/2$ when the original minimum degree is at least $(n-1)/2$. Apply the proved theorem and remove the universal vertex from its cycle. The remaining sequence is a Hamiltonian path in the original graph.

A necessary condition for a Hamiltonian cycle is that deleting a nonempty vertex set $S$ leaves at most $|S|$ components, since deleting those vertices breaks a spanning cycle into at most that many path pieces. For any $k\ge 1$, take the connected star $G=K_{1,k+2}$. In $G_k$, deleting its center and the $k$ new vertices leaves $k+2$ components, more than $k+1$. Even two-connectivity does not suffice: take $G=K_{2,k+3}$, which is two-connected. Deleting its two-vertex part and the $k$ new vertices from $G_k$ leaves $k+3$ components, more than $k+2$. Both connectivity requirements admit counterexamples for every $k$.

Suppose a graph satisfying Ore's theorem were not Hamiltonian. Extend it, on the same vertices, to an edge-maximal non-Hamiltonian graph $H$. Adding edges preserves the degree-sum hypothesis. The complete graph is Hamiltonian, so $H$ has a missing edge $uv$. By maximality, $H+uv$ has a Hamiltonian cycle, which must use the new edge. Removing it gives a Hamiltonian path in $H$, labelled $u=v_1,v_2,\dots ,v_n=v$.

If some $i$ has both edges $u{v}_{i+1}$ and $v{v}_i$, the path can be closed into the cyclecontradicting the choice of $H$. Thus the index sets $\{i:u{v}_{i+1}\in E(H)\}$ and $\{i:v{v}_i\in E(H)\}$ are disjoint subsets of $\{1,\dots ,n-1\}$. Their sizes are ${\mathrm{deg}}_{H}u$ and ${\mathrm{deg}}_{H}v$. Consequently ${\mathrm{deg}}_{H}u+{\mathrm{deg}}_{H}v\le n-1$, contradicting the degree-sum condition for the nonadjacent pair $u,v$. Hence the original graph is Hamiltonian.

Use subset dynamic programming for a Hamiltonian path, with a Boolean dynamic programming state $D[S,v]$ for each nonempty subset $S\subseteq V$ and $v\in S$. It is true exactly when there is a graph path using every vertex of $S$ once, using no other vertices, and ending at $v$. The base and transition arewhere $A$ is the adjacency matrix of a directed graph.For correctness, a valid path ending at $v$ has some penultimate vertex $u$; removing $v$ yields exactly a path recorded by the corresponding predecessor state. Conversely, extending any true predecessor state by the edge $(u,v)$ produces a path visiting precisely $S$ once. Mathematical induction on $|S|$ proves the meaning of every state. Therefore the final disjunction is true exactly when a Hamiltonian path exists.

There are $n{2}^{n-1}$ possible states and at most $n-1$ predecessor checks per state. More exactly, the full set of ordered predecessor checks has size $n(n-1)2^{n-2}$ for $n\ge 2$. With constant-time adjacency matrix access and ordinary subset-indexed table access,The graph is normally assumed nonempty here. If the empty graph is admitted, return the chosen convention for its empty Hamiltonian path separately; it does not affect the bound.

Suppose a Directed acyclic graph has a Hamiltonian path $(w_1,\dots ,w_n)$. Every edge $(w_j,w_{j+1})$ forces $w_j$ to precede $w_{j+1}$ in every topological sort. Transitivity forces the entire order $(w_1,\dots ,w_n)$, so the topological sort is unique and every consecutive pair is joined by the requisite edge. No edge can point backwards in this path order, since that edge together with part of the path would form a directed cycle.

Conversely, if a topological sort $(w_1,\dots ,w_n)$ has an edge from every entry to the next, those edges form a graph path through all vertices exactly once. Thus the displayed order is itself a Hamiltonian path.

The unique topological ordering criterion says that uniqueness alone already forces the consecutive-edge condition. If $(w_j,w_{j+1})$ were absent, swapping these adjacent entries would preserve every edge constraint: only their mutual order changes, and a reverse edge is already forbidden by the original topological sort. This would produce a second order. Consequently, for a Directed acyclic graph, having a Hamiltonian path, having a unique topological sort, and having consecutive edges in a topological sort are equivalent. The source's $>$ notation is read as “appears earlier”, consistent with its explicitly directed edges.

Compute any topological sort $(w_1,\dots ,w_n)$ using a standard algorithm, then check its consecutive entries in the adjacency matrix:If all checks pass, the returned ordering is a Hamiltonian path. If a check fails but a Hamiltonian path existed, part (d) would force the computed topological sort to equal the unique path order, whose consecutive edges all exist. This contradiction proves the negative answer correct.

A standard topological sort scans all matrix rows and therefore takes $O(n^2)$ time with this input representation; the subsequent $n-1$ edge checks take $O(n)$. The answer is consequently $O(n^2)$ time, with $O(n)$ auxiliary storage beyond the input matrix. An $O(|V|+|E|)$ bound for an adjacency list must not be substituted for the stipulated adjacency matrix bound.

The printed formula for the edge label has mismatched variable names. The type-correct reading is $x_i=\sigma (v_{i-1},v_i)$. Interpret the requested route as a directed walk of consecutive labelled edges, allowing repeated vertices; the distinction from a vertex-simple directed path is discussed below.

Let $R_t$ be the set of vertices reachable from the specified start after reading exactly the first $t$ labels. Initialize $R_0=\{v_0\}$ and updateAfter $k$ stages, answer yes exactly when $R_k\ne \varnothing$. A directed walk realizing a prefix decomposes into a walk realizing the shorter prefix and one correctly labelled final edge; conversely every such extension is valid. This proves the dynamic programming invariant by induction on $t$. Store reachable vertices in Boolean arrays and scan the edges per stage. The running time is $O(k(|V|+|E|))$ with $O(|V|)$ rolling-table space complexity, in addition to graph storage. The empty label sequence is realized by staying at $v_0$.

If “path” is instead required to mean vertex-simple, augment the state to $(S,v)$, where $S$ is the set of visited vertices. Start with $R_0(\{v_0\},v_0)$ and extend a matching edge to $w$ only when $w\notin S$, replacing $S$ by $S\cup \{w\}$. This gives an exact dynamic programming algorithm for that interpretation too; reject immediately when $k\ge |V|$. A straightforward bound is $O(k{2}^{|V|}(|V|+|E|))$ running time with $O(2^{|V|}|V|)$ rolling-table storage. The exponential distinction is substantive: all labels equal and $k=|V|-1$ include the Hamiltonian path problem from a fixed start. The efficient layered recurrence answers the consecutive-edge interpretation without pretending to enforce distinct vertices.

For a directed graph with adjacency matrix $A$, let $D[S,v]$ record whether a path visits precisely the vertices of $S$ once and ends at $v$. The singleton states are true. A larger state is true exactly when some predecessor $u\in S\setminus \{v\}$ has a true state for $S\setminus \{v\}$ and an edge to $v$. Removing or adjoining the last edge proves this recurrence by mathematical induction on $|S|$. There are $n{2}^{n-1}$ states, each requiring at most $n-1$ predecessor checks, giving $O(n^2{2}^n)$ time and $O(n{2}^n)$ storage. A true state for $S=V$ certifies a Hamiltonian path.

A finite nonempty Directed acyclic graph has a unique topological sort exactly when it has a Hamiltonian path. A Hamiltonian path forces the relative order of every consecutive pair and therefore of all vertices. Conversely, in a unique topological sort, every consecutive pair must have a forward edge: if such an edge were absent, swapping that adjacent pair would preserve all edge constraints and produce a second topological sort. The consecutive edges give a Hamiltonian path. Consequently one may compute any topological sort and test its consecutive edges, taking $O(n^2)$ time on an adjacency matrix representation.