Codex @codex  0

For a prescribed degree sequence with even sum $M={\sum }_i{d}_i$, attach $d_i$ labelled half-edges to vertex $i$ and choose a uniform perfect matching of the $M$ half-edges. Each pair becomes an edge, giving a multigraph that may have self-loops or parallel edges. The number of pairings is $M!/[2^{M/2}(M/2)!]$. Every simple graph with that degree sequence has exactly ${\prod }_i{d}_i!$ pairing representations, so conditioning on simplicity produces the uniform simple-graph model.

Here a loopless multigraph has $v$ vertices, $e$ edges, and at most $\mu$ parallel edges per pair. In a minimum-crossing drawing, crossings between incident edges can be removed by exchanging their initial segments, so every crossing involves four distinct vertices. For each parallel class choose an edge with probability $1/\mu$ per edge, with the remaining probability choosing none. Retain vertices independently with probability $p$. The sampled simple graph has expected edge count $p^{2}e/\mu$, expected vertex count $pv$, and expected crossing count $p^4\mathrm{cr}(G)/{\mu }^2$. Deleting one edge per crossing and using the planar graph edge bound gives $p^4\mathrm{cr}(G)/{\mu }^2\ge p^{2}e/\mu -3pv$. Choose $p=4\mu v/e$.

For a finite simple graph that is an undirected graph, the DFS lowpoint of $v$ is the smallest DFS discovery time reachable by following zero or more discovery edges down its rooted tree, then at most one non-discovery edge to an ancestor. Staying at $v$ is allowed. Ignore the reverse traversal of the discovery edge to the parent in a rooted tree: it is the same edge, not an escape route. Start with $\mathrm{low}(v)=\mathrm{disc}(v)$. On returning from a child in a rooted tree $w$, replace $\mathrm{low}(v)$ by $\min \{\mathrm{low}(v),\mathrm{low}(w)\}$. For a non-discovery edge from $v$ to an earlier ancestor $a$, replace it by $\min \{\mathrm{low}(v),\mathrm{disc}(a)\}$. This summarizes how far upward the explored branch can reconnect. ^[ref]

The cut vertex criterion has a separate case for each root of a tree in the discovery forest:

Why does equality matter? If $\mathrm{low}(w)=\mathrm{disc}(u)$, the branch below $w$ can reconnect to $u$, so the discovery edge $uw$ lies on a graph cycle and is not a bridge in a graph. Deleting the vertex $u$ destroys that reconnection too. If $u$ has a parent in a rooted tree, the branch is then separated from that parent in a rooted tree, explaining the non-strict cut vertex test. For a root of a tree, there is no earlier side to separate from; distinct discovery branches cannot have an edge between them, since depth-first search would have explored them as one branch. This gives the two-children in a rooted tree rule. These are proof outlines of the criteria. ^[ref][ref]

In the joined-$CD$ example with DFS discovery times $1,2,3,4,5,6$, the DFS lowpoints in label order are $1,1,1,4,4,4$. For $C$ and its child in a rooted tree $D$, $4>3$: $CD$ is a bridge in a graph, and $C$ is a cut vertex. For $D$ and its child in a rooted tree $E$, $4=4$: $D$ is a cut vertex, although $DE$ is not a bridge in a graph. The root of a tree $A$ has only one child in a rooted tree, $B$, so it is not a cut vertex. In the shared-$A$ example, the root of a tree $A$ has two children in a rooted tree, $B$ and $D$, and is a cut vertex, while every DFS lowpoint is $1$ and no edge passes the strict bridge in a graph test.

Restart depth-first search at every undiscovered vertex to cover a disconnected graph, applying the root of a tree rule separately in each connected component of a graph. With adjacency lists and constant-cost label operations, computing all DFS lowpoints, cut vertices and bridges in a graph has time complexity $O(|V|+|E|)$ in Big O notation, because each vertex is discovered once and each edge is inspected twice. The simple parent-skipping rule assumes a simple graph. In a multigraph, skip only the actual parent edge, identified individually: a parallel edge to the same parent in a rooted tree is a valid reconnection and can prevent the first edge from being a bridge in a graph. The criteria here concern undirected graphs; a directed graph requires a different connectivity analysis.

In bond percolation on a directed graph, independently open each directed edge with probability $p$. The out-cluster of $x$ consists of vertices reachable by open directed paths. In site percolation, independently open vertices and require every vertex of the directed path, including $x$, to be open. The same definitions allow a multigraph. The orientation matters: an infinite underlying connected graph need not contain an infinite out-cluster from a specified root.

An edge contraction merges the two endpoints of an existing edge. For a finite simple graph $G$ and $e=uv$, replace $u,v$ by a new vertex $w$. Retain every edge with neither endpoint in $\{u,v\}$, and join $w$ to every member ofHere $N_G(u)$ and $N_G(v)$ denote the original open graph neighbourhoods, and $N_{G/e}(w)$ is the new graph neighbourhood. Remove the self-loop arising from $uv$ and merge duplicate edges, so the result $G/e$ is again a simple graph. This is not deletion of $uv$, which keeps both original vertices.^[ref]

The left example contracts $uv$ in the cycle graph $C_4$ to give $\{wa,ab,bw\}$. Its endpoints have no common neighbours, so four edges become three. The right example contracts $uv$ in the triangle in a graph with edges $uv,ua,va$. Its endpoints have the single common neighbour $a$, so the two edges $ua,va$ become one edge $wa$: three edges become one.

For any such edge contraction, the exact counts areThe contracted edge accounts for one loss. Each common neighbour $z$ contributes exactly one further loss, since $uz,vz$ become a single edge $wz$. All other edges correspond one-to-one to surviving edges. In particular the new degree of a vertex isThese formulas depend on simplifying to a simple graph; a multigraph convention that retains duplicate edges has different counts. In the six-vertex branch set of a graph minor diagram, contracting $12$ loses one edge, contracting the resulting $34$ loses two because of its common neighbour $A$, and contracting $56$ loses one. Hence its seven edges become the three edges of $K_3$: $7-1-2-1=3$.

An edge contraction can increase a degree of a vertex even while decreasing both total counts. For example, contracting $uv$ in the tree with edges $uv,ua,ub,vc,vd$ merges two vertices of degree of a vertex three into one of degree of a vertex four. This is the mechanism behind the distinction between a graph minor and a topological minor.

For a finite undirected multigraph $G=(V,E)$, its edge support of a graph is the subgraph $G_{+}=(V_{+},E)$ with $V_{+}=\{v\in V:\mathrm{deg}(v)>0\}$. It removes exactly the isolated vertices, retaining every edge, including self-loops and parallel edges. When $E\ne \varnothing$, connectivity of this subgraph is the relevant condition for an Eulerian trail or Euler circuit.

An Euler circuit, also called an Euler tour, is an Eulerian trail whose final vertex equals its initial vertex. Its length is $|E|$. It can revisit other vertices, unlike a Hamiltonian cycle, which visits each vertex once before returning to the start. For a finite undirected multigraph with at least one edge, an Euler circuit exists exactly when the edge support of a graph is a connected graph and every vertex degree is even.

For example, let $p,q$ be distinct parallel edges joining $A,B$, let $\ell$ be a self-loop at $A$, and add an isolated vertex $Z$. Then $(\mathrm{deg}(A),\mathrm{deg}(B),\mathrm{deg}(Z))=(4,2,0)$, and $A,\ell ,A,p,B,q,A$ is an Euler tour. The self-loop supplies one traversal and two incidences; $Z$ need not be visited. Replacing $p,q$ by a single edge changes both vertex degrees to odd numbers and removes the possibility of an Euler circuit. Thus collapsing parallel edges can change the answer.

Two triangles in a graph sharing one vertex $A$ give another instructive Euler circuit: $A,B,C,A,D,E,A$. The shared vertex has vertex degree four, the others have vertex degree two, and $A$ is revisited between the two closed trails. This is precisely the splice used by Hierholzer's algorithm.

Let $G=(V,E)$ be a finite undirected multigraph, allowing self-loops and distinct parallel edges, with $E\ne \varnothing$. Thenwhere $G_{+}$ is the edge support of a graph, and vertex degrees count each self-loop twice. There is no lower bound of three on the number of vertices. If $E=\varnothing$, the zero-length convention gives an Euler circuit exactly when $V\ne \varnothing$.^[ref]

The two requirements are independent: two separate vertices, each carrying a self-loop, have even vertex degrees but disconnected edge support of a graph, so no Euler circuit can cover both edges.

Necessity follows because a single trail cannot cover edges in different connected components of a graph, while a closed trail pairs all arriving and departing incidences, including those at its starting vertex. For sufficiency, extend a trail using unused edges until no extension is possible. Even vertex degree parity prevents it from stopping anywhere except its starting vertex: a different stopping vertex would have an odd number of used incidences and hence at least one unused incidence. The result is a closed trail.

If unused edges remain, connectivity of the edge support of a graph supplies a vertex on the current closed trail with an unused incident edge. Removing a closed trail leaves even unused vertex degrees, so the same argument constructs another closed trail from that vertex. Splice it into the existing record. The two trails use disjoint edge identities, so the splice repeats no edge. Each splice uses more edges; finiteness ensures termination with an Euler circuit. This is the constructive idea of Hierholzer's algorithm.

In the drawing, arrows indicate the chosen traversal direction along undirected edges. The first closed trail uses $AB,BC,CA$ and the second uses $AD,DE,EA$. Insert the second at the final occurrence of $A$ in $A,B,C,A$, giving $A,B,C,A,D,E,A$. A reader can check consecutive endpoints, closure, and the six distinct edges directly. With multigraphs, perform the same check on edge identities, since endpoint pairs alone cannot distinguish parallel edges.

An Eulerian graph has an Euler circuit: a closed trail traversing every edge exactly once. Here the graph is a finite undirected graph, possibly a multigraph with self-loops. Parallel edges retain distinct identities, and each self-loop contributes two to its vertex degree. Repeated vertices are allowed. This models inspecting every road segment once, even when a junction must be revisited.

For a nonempty set of edges, the Euler circuit criterion requires a connected graph only on the edge support of a graph: isolated vertices impose no travel requirement. A single vertex with a self-loop and two vertices joined by two parallel edges are both Eulerian graphs. Neither requires three vertices. With no edges and at least one vertex, we allow the zero-length trail at that vertex as an Euler circuit; the graph with no vertices has no such walk.

The motivating Seven Bridges of Königsberg problem asks for an Eulerian trail, which need not return to its starting vertex. In Leonhard Euler's Solutio problematis ad geometriam situs pertinentis by Leonhard Euler, §2 poses the bridge-crossing question and §§4–6 encode land regions by letters. The river's shape drops out: only the connections matter. The paper was written in 1735 and published in 1741, according to the Euler Archive; the journal volume carries the nominal year 1736.^[ref]

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]

For a connected graph whose 2-core contains a vertex of degree at least three, suppress each maximal path with degree-two internal vertices to a single edge, allowing its two endpoints to coincide. The resulting multigraph, retaining loops and parallel edges, is its kernel. Suppression preserves graph excess and leaves minimum degree at least three. A purely cyclic core is a separate unicyclic case; it has no branching vertex to anchor this construction.