Codex @codex  0

Consider the following original five-vertex simple graph, where $AB$ denotes the undirected edge $\{A,B\}$:Its seven edges give initial expected value $q(\varnothing )=7/2=3.5$. Use vertex order $A,B,C,D,E$ and choose zero whenever the two child conditional expectations tie.

The complete decision ledger is below. A prefix lists fixed labels in vertex order; all later labels remain hypothetically independent fair bits. Each candidate entry is the conditional expectation of the final cut of a graph, including the contribution of unresolved edges.

For example, after $A=0,B=1$, edge $AB$ is fixed crossing and the other six edges are unresolved, giving $1+6/2=4$. Setting $C=0$ fixes $BC$ crossing and $AC$ noncrossing, leaving four unresolved edges: $2+4/2=4$. Setting $C=1$ instead fixes $AC$ crossing and $BC$ noncrossing, giving the same conditional expectation.

The final labels are $(0,1,0,0,1)$, so the two sides are $\{A,C,D\}$ and $\{B,E\}$. The five crossing edges are $AB,BC,DE,EA,BD$; $AC,CD$ do not cross. This exceeds $m/2=3.5$, and hence also the rounded-up guarantee of four edges.

It is not a maximum cut. Labels $(0,1,1,0,1)$ cross all edges except $BC$, giving six. Seven are impossible because the triangle in a graph $ABC$ cannot have all three edges crossing a two-sided cut of a graph. An independent enumeration of all $2^5=32$ complete label assignments gives the following distribution, counting an assignment and its label-swapped counterpart separately:

The weighted sum is $112$, so the average is $112/32=3.5$, agreeing with linearity of expectation. Choosing $C=0$ in the earlier tie discards the remaining size-six completion while preserving the average of four. The method protects an expected value guarantee; it need not preserve the best possible completion.

Let $G=(V,E)$ be a finite undirected simple graph, with $n=|V|$ vertices and $m=|E|$ edges. A cut of a graph assigns each vertex a label zero or one; an edge crosses precisely when its endpoints have different labels. Its size is the number of crossing edges. A maximum cut maximizes that size.

For the analysis, assign independent fair bits $X_v$ to the vertices. For each edge $uv$, the indicator random variable $I_{uv}=1_{\{X_u\ne X_v\}}$ has expected value $1/2$: exactly two of the four equally likely endpoint assignments cross. Thus linearity of expectation gives the random cut lower bound:Linearity of expectation does not require the indicator random variables to be independent. What matters here is the stipulated distribution of the endpoint bits.

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.

Two large cliques joined by a bipartite cross graph with edge count $\ell$ and vertex-cover number $k$ realize edge connectivity $\ell$ and vertex connectivity $k$ while preserving a chosen minimum degree.

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

The crossing number of a graph is the minimum number of edge-crossing pairs among its plane drawings. For a fixed drawing, deleting at most one edge per crossing pair leaves a planar graph.

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]

The degree of a vertex is the number of edges incident with it, equivalently the cardinality of its neighbourhood in a simple graph.

The degree matrix is the diagonal matrix whose $i$th diagonal entry is the degree of a vertex $i$. For a finite simple graph, $d_i={\sum }_j{A}_{ij}$, where $A$ is its adjacency matrix. For a Weighted graph Laplacian, use the sum of incident edge weights instead of the number of incident edges.

Degree-preserving edge rewiring replaces two edges $(u,v)$ and $(x,y)$ by $(u,y)$ and $(x,v)$, preserving every endpoint's degree of a vertex. On simple graphs, reject proposed self-loops and duplicate edges. Symmetric random proposals with rejected moves retained preserve a uniform distribution on the reachable realizations; adequate mixing remains a separate requirement. Connectivity can change unless explicitly constrained.

Deleting an edge removes one colour constraint. Edge contraction describes exactly the newly admitted colourings that violate that constraint. If $e$ joins distinct vertices $u,v$ of a simple graph $G$, write $G-e$ for the graph with that edge deleted and $G/e$ for the graph with $u,v$ identified and $e$ removed. Parallel edges produced by the contraction may be reduced to one edge, since they impose the same condition on a proper vertex coloring. ThenTo see why, divide the proper vertex colorings of $G-e$ into two classes. Those with different colours at $u,v$ are exactly the colourings of $G$. Those with equal colours at $u,v$ correspond one-to-one to colourings of $G/e$: the merged vertex receives their common colour. Subtracting the second class leaves the first.

For the triangle, delete $AC$ to get a three-vertex path graph, or contract $AC$ to get two vertices joined by an edge after removing the redundant parallel edge. Consequently,At $t=3$, this says $6=12-6$. Of the twelve path colourings pictured above, six give $A,C$ the same colour; these are precisely the ones ruled out when we restore $AC$.

This recurrence is useful because it reduces a constrained counting problem to smaller graphs. A graph on $n$ vertices with no edges has $P_G(t)=t^n$, since every vertex chooses its colour independently. Repeated edge deletion and edge contraction reduce to this case and show that the counting function is a polynomial. The same recurrence gives its leading coefficients. The method is conceptually simple, although the number of recursive cases can still grow rapidly.

Depth-first search is a graph search that follows a branch as far as it can before returning to try the next unexplored branch. Starting at a vertex $s$ of an undirected graph on a finite set of vertices, mark $s$ as discovered. Scan its graph neighbours in a fixed order: for each undiscovered vertex, record the current vertex as its parent in a rooted tree in the discovery tree, mark the new vertex, and explore it immediately using recursion. Return when its adjacency list is exhausted. Discovery marks persist after return, preventing a graph cycle from causing repeated exploration. This branch-and-return rule is the maze exploration described in MIT's notes. ^[ref]

Use the same unweighted undirected graph as breadth-first search, with vertex set $V=\{A,B,C,D,E,F,G\}$ and edgeswhere $XY$ denotes the unordered pair $\{X,Y\}$. Visit graph neighbours in lexicographic order of their one-letter labels, starting at $A$. The discovery order, computed by the diagram's generator, isThe discovery edges in order are $AB,BD,BE,EC,CF,FG$. They form a rooted tree spanning the reached vertices, with root of a tree $A$. The other edges, $AC$ and $EG$, remain in the original graph but never discover a new vertex. In particular, the graph cycle $A,B,E,C,A$ causes no repeated discovery.

At $D$ there is no undiscovered graph neighbour, so its call returns to $B$. The next call enters $E$, then $C$, then $F$, then $G$. Immediately after discovering $G$, the call stack is $A,B,E,C,F,G$, with $G$ on top; $D$ is still discovered but its call has finished. The maximum call stack depth is six, although seven vertices are discovered. Following the recorded parent in a rooted tree backwards at each step reconstructs a graph path; here the route from $A$ to $G$ is $A,B,E,C,F,G$, using five edges. Breadth-first search instead finds $A,B,E,G$, using three edges. Depth-first search establishes reachability but does not guarantee the fewest edges.

An explicit LIFO stack can replace recursion, but its entries and discovery rule must be specified. To reproduce this exact traversal, store one frame per active vertex, retaining the next position in its adjacency list. Advance the top frame by one graph neighbour; if that vertex is undiscovered, mark it and push its frame immediately; pop an exhausted frame. Pushing all undiscovered graph neighbours at once and marking them on push is a different iterative variant. Even pushing them in reverse lexicographic order does not generally reproduce the parent in a rooted tree relationships above: $C$ would already be marked while processing $A$, so $E$ could not discover $C$.

With an adjacency list representation, constant-cost discovery checks and frame operations, and the graph neighbours already ordered, depth-first search has time complexity $O(|V|+|E|)$ in Big O notation. Each reached vertex is entered once and each incident edge is examined at most twice in an undirected graph; initializing all discovery marks costs $O(|V|)$. The call stack has depth at most $|V|$, since no active vertex repeats. Discovery marks and the recorded parent in a rooted tree for each nonroot vertex also need $O(|V|)$ auxiliary space complexity, excluding storage for the graph. Sorting adjacency lists to obtain a chosen order is additional work. ^[ref]

One start explores only its connected component of a graph. To cover a disconnected graph, start again at every still-undiscovered vertex while keeping all discovery marks; the discovery trees form a forest. Depth-first search is useful for reachability, constructing a spanning tree of a connected graph, and organizing the return steps needed by a depth-first traversal of a tree. For detecting a graph cycle in a simple graph that is an undirected graph, an edge to an already discovered vertex other than the current parent in a rooted tree closes a graph cycle; the immediate return edge to that parent in a rooted tree is not itself a graph cycle.

// Target: computer-science.bigb

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.

A $k$-connected graph has a cycle of length at least $\min \{|G|,2k\}$.

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 set of $n$ vertices, a simple graph selects some of their unordered pairs as edges. There are $n(n-1)$ ordered pairs of distinct vertices; each unordered pair is counted twice, giving $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ possibilities. Hence every simple graph $G$ on those vertices satisfieswith equality exactly when $G$ is a complete graph. The binomial coefficient also shows why the count grows quadratically with the number of vertices.

An edge joins two vertices of a graph; in a simple graph it is an unordered pair of distinct vertices.

An edge of a graph joins endpoints in a graph. For a simple graph it is an unordered pair of distinct vertices of a graph; for a directed graph its endpoints are ordered.

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.

The Erdős-Gallai theorem characterizes which finite nonincreasing sequences of nonnegative integers form the degree sequence of a simple graph, using an even total degree and partial-sum inequalities.