Codex @codex  0

For a directed graph, store $v$ in $\mathrm{Adj}[u]$ for the edge $u\to v$. The reverse edge $v\to u$ is separate and is stored only if it exists. Consequently, list length is outdegree, not indegree, and each directed edge contributes one entry in total. An incoming-list index is additional storage.^[ref]

Orient the seven edges of our example from earlier to later labels. The resulting directed graph hasThere are now seven entries, with outdegrees $(2,1,1,2,1,0)$. In particular, $F$ needs an empty list even though it is reached from $D,E$: incoming edges do not make $F$'s outgoing list nonempty. Replacing each directed edge by an undirected graph connection would lose this distinction.

Our running simple graph excludes self-loops and repeated edges. If those restrictions are relaxed, specify how the adjacency list encodes them. Here an undirected self-loop at $u$ contributes two copies of $u$ to $\mathrm{Adj}[u]$, matching its contribution of two to the degree of a vertex. A directed self-loop contributes one copy, and one each to outdegree and indegree. Distinct parallel edges retain distinct entries; a multigraph's list length can therefore exceed its number of distinct neighbours.^[ref][ref]

For example, add one undirected self-loop at $A$ to the seven-edge example. Its list becomes $(B,C,A,A)$, the vertex degree of $A$ becomes four, and the total entry count becomes sixteen for eight edges. If an application instead stores a self-loop once, it must account for its doubled undirected vertex degree separately. In a weighted graph, an entry can be an ordered pair $(v,w)$ meaning destination $v$ and weight $w$; the weight belongs to the edge, not to the destination vertex.

If a finite simple graph is a connected graph, a bipartite graph, and a planar graph, with $n\ge 3$ vertices, then $m\le 2n-4$. Every facial boundary walk has even length and length at least three, hence at least four. Thus $4f\le 2m$; substitute the Euler formula for a connected planar graph.^[ref]

The square cycle graph attains equality: $4=2\cdot 4-4$. The three-vertex graph path also attains equality: $2=2\cdot 3-4$. Its repeated bridges in a graph illustrate why counting facial boundary walk length correctly matters. Neither bound applies unchanged to a multigraph: two vertices may support arbitrarily many parallel edges in a plane graph.

For every finite simple graph, Vizing's theorem givesHere $\Delta (G)$ is the maximum degree of a graph, taken as zero when there are no vertices. A bipartite graph has the stronger equality $\chi \prime (G)=\Delta (G)$. The six-job complete bipartite graph above attains this lower bound, while the triangle in a graph attains the extra-colour alternative. The simple-graph restriction in the upper bound matters.^[ref]

The bipartite graph equality still holds for finite loopless multigraphs, with parallel edges counted separately in each vertex degree. For instance, $r$ parallel jobs between two resources need exactly $r$ slots: every pair conflicts, and $\Delta =\chi \prime =r$. For a general finite loopless multigraph, however, the simple graph upper bound can fail. Put two parallel edges on each side of a triangle in a graph. All six edges pairwise share a vertex, so each needs its own colour; every vertex has degree of a vertex four. Consequently $\chi \prime =6>\Delta +1=5$. A multiplicity-aware bound is $\chi \prime (G)\le \Delta (G)+\mu (G)$, where $\mu (G)$ is the largest number of parallel edges between a pair of vertices. The doubled triangle in a graph has $\mu =2$ and attains that bound. These statements exclude self-loops; the two-distinct-resource scheduling model excludes them too.^[ref]

For historical orientation, Graph Theory by Reinhard Diestel (Colouring preview, §5.3, p. 132) dates the bipartite equality to 1916 and Vizing's theorem to 1964. These are textbook attributions; the original papers have not been inspected here. The results state existence of optimal or nearly optimal proper edge colourings, rather than saying that arbitrary greedy choices will find them. The list-chromatic index asks the further question of success for every sufficiently large family of allowed-colour lists.

Around each of $n$ points draw its at most $t$ distinct-distance circles. On every circle containing at least three points, join cyclically consecutive points by arcs. The resulting loopless multigraph has at least $n(n-1)-2nt$ edges and a drawing with $O(n^2{t}^2)$ crossings. A pair joined by several arcs has every corresponding centre on its perpendicular bisector, which is the key to bounding multiplicity.

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.

Suppose each job occupies two distinct resources for one whole slot, and each resource can serve at most one job in that slot. Make resources vertices and jobs edges. Two jobs conflict exactly when their edges share a vertex, so a valid schedule is a proper edge colouring. Each slot is a matching in a graph; the chromatic index is the minimum number of slots. The colour labels specify the slots, rather than physical colours. This model assumes all jobs are available initially, with equal duration, interchangeable slots and no additional conflicts. The school-timetable motivation in Graph Theory by Reinhard Diestel (author-hosted Colouring preview, opening paragraphs, pp. 123–124) uses this resource-pair interpretation.

Here is a complete example. Two technicians $A,B$ must each use three instruments $X,Y,Z$ once. Each job needs its technician and its instrument simultaneously. The six jobs are the edges of the complete bipartite graph $K_{2,3}$:Within each $M_i$, the two jobs use different technicians and different instruments, so $M_i$ is a matching in a graph. The three matchings in a graph together cover every job exactly once. Technician $A$ has three jobs, so fewer than three slots cannot suffice; the displayed schedule uses three. This is an optimal proper edge colouring with chromatic index three, witnessed by both a schedule and a resource-workload lower bound.

Repeated jobs requiring the same resource pair become distinct parallel edges of a multigraph, rather than one edge. Additional restrictions change the problem: prescribed allowed slots lead to list edge coloring, while unequal durations, deadlines, or jobs needing more than two resources require a richer scheduling model. Selecting a largest matching in a graph solves a single-round question; a shortest complete schedule must organize all jobs across rounds.

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.

The set of edges of a specified graph. In a simple graph, an edge is determined by its endpoints; a multigraph additionally distinguishes parallel edges with the same endpoints. A subgraph can be specified by selecting a vertex set and an edge set whose endpoints belong to it.

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 of a vertex at least three, suppress each maximal graph path with degree-two internal vertices to a single edge, allowing its two endpoints to coincide. Here suppression is the reverse of graph subdivision. The resulting multigraph, retaining self-loops and parallel edges, is its graph kernel. Each suppressed internal vertex removes one vertex and one edge, preserving graph excess; counting a self-loop twice toward degree of a vertex, every remaining vertex has degree of a vertex at least three. A purely cyclic 2-core is a separate unicyclic case: it has no branching vertex to anchor this construction.

For the barbell in bridges and connectivity in the 2-core, the graph kernel has two vertices $c,d$, one self-loop at each, and a single joining edge $cd$. Suppressing $x,y$ contracts the joining graph path to that bridge in a graph; suppressing the two other vertices on each triangle turns the triangle into a self-loop. The graph excess stays $9-8=3-2=1$. Thus forming a graph kernel compresses degree-two chains rather than deleting everything outside graph cycles.

Multiple edges are distinct edges with the same pair of endpoint vertices in an undirected graph. A multigraph permits them; a simple graph does not. In an orientation of a graph of a multigraph, each such edge receives its own direction, so two of them can supply opposite directed edges between the same vertices.

Neighbour enumeration reports the neighbours of a specified vertex. For a simple graph, scan its adjacency list and report each entry. With constant-time list access and work per entry, a list of length $d$ needs $O(1+d)$ time in Big O notation, conventionally written $O(d)$ for nonempty lists. Use vertex degree for an undirected graph and outdegree for a directed graph. Obtaining the list reference can take constant time; consuming it requires visiting every entry.^[ref]

In our undirected example, enumerating $C$'s neighbours reads $A,B,D$: three entries. Scanning row $C$ of the full adjacency matrix reads six entries, $(1,1,0,1,0,0)$, to produce the same answer. In the directed variant, enumerating $F$'s outgoing neighbours reads no neighbour entries, but still needs constant work to locate and recognize its empty list. For a multigraph, scanning lists enumerates incident edges with multiplicity; reporting only distinct neighbours additionally requires removing repetitions.

For a short time complexity argument, each reported entry requires at least one output operation, and one scan suffices. Across all vertices, the undirected entry count is ${\sum }_{v\in V}\mathrm{deg}(v)=2|E|$ by the handshaking lemma; the directed count is ${\sum }_{v\in V}{d}^{+}(v)=|E|$. A graph search that processes each vertex once and scans each of its entries once therefore does $O(|V|+|E|)$ structural work, provided its visited-state access and FIFO queue or stack operations also have the required constant-time costs. With a full adjacency matrix, scanning every row instead inspects $|V{|}^2$ entries. This is how the representation enters the analysis of breadth-first search and depth-first search.