Codex @codex  0

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.

For a finite connected graph embedded as a plane graph, follow the edges around a face of a plane graph to obtain a closed walk. Count traversals, not distinct edges: a bridge in a graph occurs twice along one facial boundary walk. Each edge contributes two sides in total.^[ref]

For the three-vertex graph path $A-B-C$, the only facial boundary walk is $A,B,C,B,A$, of length four. Both edges are bridges in a graph; neither is a graph cycle. Thus a facial boundary walk need not be a graph cycle.

For a finite connected unweighted loopless graph with $n$ graph vertices,The edge-inclusion formula for a uniform spanning tree gives the left-hand side as $\mathbb{E}|T|$, and every spanning tree has $n-1$ edges. On the same finite connected graph with positive edge conductances $c_e>0$, the corresponding identity is ${\sum }_e{c}_e{R}_{\mathrm{eff}}(e)=n-1$.

Here excess means edges minus vertices. For a connected graph it is one less than the number of independent cycles. Deleting a leaf and its incident edge, or suppressing a degree-two vertex, preserves excess. This convention differs by one from the cyclomatic number for connected graphs.

For a finite undirected graph, the graphic matroid has its edges as the ground set. A subset is a matroid independent set when its edges form a forest on the original vertices, including isolated vertices. Its matroid bases give a spanning tree in each connected component of a graph; for a connected graph, each matroid basis is a spanning tree.

For a graph triangle on vertices $P,Q,R$, label the edges $a=PQ$, $b=QR$, and $c=PR$, with weights $8,5,6$. The empty set, all singletons, and all pairs are forests; the triple contains the graph cycle $P,Q,R,P$. Thus its eight subsets have exactly the independence pattern checked in the weighted three-vector matroid, and the same fifteen exchange comparisons pass. The matroid greedy algorithm chooses $PQ$, chooses $PR$, and rejects $QR$, producing the heaviest spanning tree, of weight $14$.

Exchange outline. Deleting edges cannot create a graph cycle. If forests $I,J$ have $|I|<|J|$, some edge of $J$ joins different connected components of a graph of $I$: otherwise, within each such component, $J$ would have at most its number of vertices minus one edges, giving $|J|\le |I|$. Adding that edge keeps a forest. This is the matroid independence axioms expressed through connectivity.

A graph minor compresses connected regions of a graph into single vertices while retaining selected connections between them. For finite simple graphs, $H\preccurlyeq G$ means that some sequence of deleting vertices, deleting edges, and performing edge contractions produces $H$ up to graph isomorphism. Deleting a vertex also deletes all its incident edges; deleting an edge leaves its endpoints. The edge contraction convention here removes resulting self-loops and duplicate edges.^[ref]

For an exact small example, let $G$ be the cycle graph $C_4$ with vertices $u,v,a,b$ and edges $uv,va,ab,bu$. Contract $uv$ to a new vertex $w$. The surviving edges are $wa,ab,bw$, giving the complete graph $K_3$. Thus $K_3\preccurlyeq C_4$, although $C_4$ has no triangle in a graph as a subgraph. The branch sets of a graph minor are $\{u,v\},\{a\},\{b\}$, with the original edges $va,ab,bu$ witnessing all three required adjacencies. The first panel of the edge contraction diagram shows this operation.

A subgraph uses existing vertices and edges; a topological minor permits a graph subdivision of the target as a subgraph, so target edges become graph paths with mutually disjoint interiors and no target vertex in an interior. An ordinary graph minor permits whole connected branch sets of a graph minor in place of target vertices. Every topological minor is a graph minor, by contracting the replacement graph paths.^[ref]

The converse fails. Take the tree with edges $uv,ua,ub,vc,vd$. Contracting $uv$ gives the star graph $K_{1,4}$. Yet the original tree has maximum degree three, whereas every graph subdivision of $K_{1,4}$ retains a centre of degree of a vertex four. Hence $K_{1,4}$ is a graph minor but not a topological minor of this tree. The difference is that a connected branch set of a graph minor may gather connections incident to several original vertices.

The counts of vertices and edges never increase under these operations. However, the $C_4$ example shows that being a bipartite graph is not preserved: its graph minor $K_3$ contains an odd cycle. Its chromatic number also increases from two to three. A connected graph stays connected under an edge contraction, because the image of each graph path still connects its endpoints, but deletion can disconnect it. Thus one must check the particular graph property before treating it as preserved by taking graph minors.

Being a planar graph is preserved: in a crossing-free drawing, shrink a contracted edge and bring its incident edges into the merged vertex; deletion merely removes parts of the drawing. This makes a nonplanar graph minor a certificate that the original graph is nonplanar. More strongly, for a finite simple graph, being a planar graph is equivalent to having neither the complete graph $K_5$ nor the complete bipartite graph $K_{3,3}$ as a graph minor. Finding the corresponding branch sets of a graph minor settles nonplanarity even when no literal $K_5$ or $K_{3,3}$ subgraph is present. The converse is a substantial theorem, rather than a consequence of preservation alone.^[ref]

A real function $h$ on a finite connected graph satisfying $Lh=0$ everywhere is constant. At a maximum graph vertex, the identity $\mathrm{deg}(u)h(u)={\sum }_{v\sim u}h(v)$ forces every graph neighbour to have the same maximum. Connectedness propagates it to every graph vertex. This proves uniqueness of voltage up to an additive constant, and identifies sums of oppositely directed occupation voltages.

For a connected graph, the Moore-Penrose inverse of its oriented incidence matrix satisfies $D^{†}D=I-{\Pi }_1$, because this product is the orthogonal projection onto $(\ker D{)}^{\perp }$. Thus every signal decomposes into its constant mean and $D^{†}D\theta$. Writing $L={\max }_e\Vert (D^{†}{)}_{\cdot ,e}{\Vert }_2$, a sub-Gaussian random vector noise gives a simultaneous bound on $\Vert (D^{†}{)}^{\top }z{\Vert }_{\infty }$ with scale $L\sqrt{\log (m/\delta )}$.

In a finite unweighted connected graph, take distinct graph vertices $a\ne z$ and orient the unique graph path from $a$ to $z$ in a uniform spanning tree and assign signed unit current to its edges. Its mean over trees is the electrical unit flow from $a$ to $z$. The Kirchhoff node law follows by averaging graph path divergences. For the graph cycle law, let ${\mathcal{F}}_{az}$ be the two-component spanning forests separating the terminals and $A_F$ the component containing $a$. Deleting a tree-path edge and conversely adjoining an edge across a forest cut are inverse operations. Hence the mean signed current on an edge $u\to v$ isThis is the gradient of $h(u)=|\mathcal{T}(G){|}^{-1}{\sum }_F{1}_{A_F}(u)$, proving the graph cycle law. In particular $R_{\mathrm{eff}}(a,z)=|{\mathcal{F}}_{az}|/|\mathcal{T}(G)|$. For an oriented existing edge $e=(a,z)$, that edge is used by the tree graph path exactly when it belongs to the tree, and then has positive orientation. Thus its mean current is $\mathbb{P}(e\in T)$, giving the edge-inclusion formula for a uniform spanning tree by Ohm's law.

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]

The complete graph $K_5$ has $n=5$ and $m=\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$, exceeding the planar graph edge bound $3\cdot 5-6=9$. Therefore it is not a planar graph. The complete bipartite graph $K_{3,3}$ has $n=6$ and $m=3\cdot 3=9$. The general bound allows twelve edges, but the bipartite planar graph edge bound allows only eight, proving nonplanarity.

These are necessary bounds, not a complete planarity test. For an original counterexample, subdivide every edge of $K_{3,3}$ once. The resulting simple graph is a connected graph with $n=15$, $m=18$, and is bipartite: put all original vertices in one part and all nine new vertices in the other. Both inequalities hold, $18\le 39$ and $18\le 26$. Nevertheless, a crossing-free graph drawing would let us trace each two-edge graph path as one curve, producing an impossible embedding of $K_{3,3}$. The graph subdivision preserves this obstruction. Kuratowski's theorem supplies a stronger characterization than these counts.

An oriented incidence matrix records an arbitrarily chosen orientation of each edge of a graph. Use one row per edge, with $+1$ and $-1$ at its endpoints and zeros elsewhere; the transpose convention is also common. The product $D\theta$ records endpoint differences. For a connected graph, $\ker D=\mathrm{span}\{1\}$, since zero difference propagates along every graph path.

A linked graph is $k$-linked if it has at least $2k$ vertices and, for every choice of distinct terminals $s_1,\dots ,s_k,t_1,\dots ,t_k$, it has pairwise vertex-disjoint graph paths joining $s_i$ to $t_i$ for all $i$. The pairing is prescribed, which is stronger than the unpaired conclusion of the Menger theorem.

We prove the rooted dense minor linkage step carefully. We first prove the rooted branch-set reduction. Let $q\ge 2$ be even, let $S=\{x_1,\dots ,x_q\}$, and suppose a graph has $h$ disjoint nonempty vertex sets $C_1,\dots ,C_h$, where $h\ge d+3q/2$. Suppose each $G[C_i]$ is connected or every one of its graph components meets $S$, and each $C_i$ is adjacent to all but at most $d$ of the other $C_j$ not meeting $S$. Assume also that no rooted separation of a graph of order below $q$ avoids $d+1$ of these sets. Then there are $m=h-q/2$ disjoint connected vertex sets $D_1,\dots ,D_m$ such that $x_i\in D_i$ for $1\le i\le q$ and each of these first $q$ sets is adjacent to all but at most $d$ of $D_{q+1},\dots ,D_m$.

Here adjacency of sets means existence of an edge between them. A rooted separation of a graph is $(A,B)$ with $A\cup B=V(G)$, $S\subseteq A$, no edges between $A\setminus B$ and $B\setminus A$, and order $|A\cap B|$. It avoids $C_i$ when $A\cap C_i=\varnothing$. We prove the reduction by induction, first on the vertex count and then on the edge count; any counterexample chosen minimal in this ordering will be impossible.

We may delete edges joining two vertices of $S$. They cannot affect rooted separations of a graph, since $S$ lies wholly on the first side. Within a branch set, their deletion can only split a graph component into graph components each containing an endpoint in $S$, so the branch-set hypothesis also persists. An isolated vertex outside $S$ and all branch sets can be deleted. An isolated vertex $v\in S$ is also impossible, since $(S,V(G)\setminus \{v\})$ has order $q-1$ and avoids at least $h-q\ge d+q/2\ge d+1$ sets. Thus in a minimal counterexample $S$ is independent, and every isolated vertex outside $S$ belongs to a singleton branch set.

Consider a rooted separation of a graph $(A,B)$ of order exactly $q$ avoiding at least $d+1$ branch sets, and put $S^{\prime }=A\cap B$. Restrict to $G^{\prime }=G[B]-E(G[S^{\prime }])$ and $C_i^{\prime }=C_i\cap B$. Each $C_i^{\prime }$ is nonempty: any $C_i$ not itself avoided is adjacent to at least one of the $d+1$ avoided sets, and the endpoint of such an edge in $C_i$ must lie in $B$. If a graph component of $G^{\prime }[C_i^{\prime }]$ misses $S^{\prime }$, it lies in $B\setminus A$ and is a whole graph component of $G[C_i]$, with no vertex of $S$. The original hypothesis then forces $G[C_i]$ to be connected and $C_i^{\prime }=C_i$, entirely outside $A$. Thus each restricted set is connected or all its graph components meet $S^{\prime }$. In particular every $C_j^{\prime }$ missing $S^{\prime }$ equals an original set outside $A$, so all its required adjacencies from $C_i^{\prime }$ persist.

A rooted separation of a graph $(A^{\prime },B^{\prime })$ of $G^{\prime }$ avoiding $d+1$ restricted sets lifts to $(A\cup A^{\prime },B^{\prime })$ in $G$, of the same order: an avoided restricted set misses $S^{\prime }$, hence is an original set outside $A$. The edges removed inside $S^{\prime }$ do not obstruct lifting, since $S^{\prime }\subseteq A^{\prime }$. This proves the required separation hypothesis for $G^{\prime }$. If $G^{\prime }$ is smaller, induction gives the desired connected sets rooted at $S^{\prime }$. Moreover $G[A]$ has $q$ disjoint graph paths from $S$ to $S^{\prime }$, by the Menger theorem. Indeed a separator of smaller order between these sets would give a rooted separation of a graph of $G$ of smaller order still avoiding those $d+1$ original sets. Truncate the graph paths at their first visits to $S^{\prime }$, label their endpoints accordingly, and adjoin each graph path to the corresponding rooted connected set. They meet $B$ only in their distinct endpoints, so this gives the desired sets for $G$, a contradiction. Consequently in a minimal counterexample every such separation of order $q$ has $B=V(G)$ and $A=S$, an independent set.

Now contract any edge whose endpoints do not belong to two different branch sets. Its endpoints cannot both lie in $S$, so the image of $S$ still has size $q$. The branch-set conditions persist. If the contraction created a forbidden rooted separation of a graph of order below $q$, its lift would have order below $q$, except possibly when the contracted vertex lies in its separator. In that case the lifted order increases by one and is at most $q$. Equality would put the contracted edge inside $A$, contradicting the just-proved independence of $A$ for an order-$q$ separation avoiding $d+1$ sets. Thus the separation hypothesis also persists. Applying induction in the contracted graph and expanding the contracted vertex would produce the required disjoint connected sets. Hence every edge in a minimal counterexample joins two different branch sets.

Every vertex outside the branch sets would be isolated, since every edge joins two branch sets; such an isolated vertex could be deleted. Thus the branch sets cover the graph. Each nonsingleton branch set is therefore an independent set, and all its vertices belong to $S$, because each of its singleton graph components must meet $S$. Let $C$ be the union of the nonsingleton branch sets, and write $c=|C|\le q$. There is a matching in a graph from $C$ into $V(G)\setminus S$. Otherwise the Hall marriage theorem gives $X\subseteq C$ with neighbourhood $Y\subseteq V(G)\setminus S$ satisfying $|Y|<|X|$. Since $S$ is independent, $(S\cup Y,V(G)\setminus X)$ is a rooted separation of a graph of order $q-|X|+|Y|<q$. It avoids every singleton branch set outside $S\cup Y$, of which there are at leastThe penultimate counting bound uses that the nonsingleton sets number at most $c/2$, so $|V(G)|-c\ge h-c/2$. This contradicts the separation hypothesis.

Use that matching in a graph to make a two-vertex connected set for each terminal in $C$; terminals outside $C$ remain singleton sets. There are at leastunused vertices, all singleton original branch sets. Choose $m-q$ of them for the remaining $D_i$. Every rooted $D_i$ contains a singleton original branch set: either its terminal, or its terminal's matched neighbour. That singleton misses at most $d$ of the selected nonterminal singleton sets. This constructs exactly the desired family, contradicting minimality and proving the branch-set reduction.

Return to the given $22k$-connected graph. By the allowed assumption it has a graph minor $H$ with $2\delta (H)\ge h+4k-1$, where $h=|H|$. Put $d=h-1-\delta (H)$. ThenTake a branch-set model of $H$ and the $2k$ prescribed terminals as $S$. The branch sets are connected and each misses at most $d$ of the others. The separation hypothesis holds with $q=2k$: a separation of order below $2k$ avoiding a branch set would separate a surviving terminal from that set, contrary even to $2k$-connectivity. Since $h\ge d+3k$, the reduction applies. It produces $m=h-k$ sets with $s_i\in D_i$, $t_i\in D_{k+i}$, each terminal set missing at most $d$ of the $m-2k$ nonterminal sets. For each pair $D_i,D_{k+i}$ at leastnonterminal sets are adjacent to both. Choose different such sets for the $k$ pairs successively. The connected graph property inside the three sets and the two joining edges give a graph path from $s_i$ to $t_i$; take a simple graph path within their union. Different graph paths use disjoint sets. We have provedIn fact the argument proves the stronger transfer statement with $2k$-connectivity and the stated dense graph minor.

For the negative assertion, it suffices to give a value of $k$ for which the proposed general implication fails. Take $k=2$ and the graph on cyclic indices $0,\dots ,7$ in which two indices are adjacent when their cyclic distance is one or two. This is the four-connected planar obstruction to two-linkage. Draw the even cycle in a graph $0,2,4,6$ as the outer square, the odd cycle in a graph $1,3,5,7$ as an inner square rotated by $45$ degrees of vertices, and join each odd vertex to the two neighbouring even vertices; the annulus is triangulated without crossings. The outer face has vertices $0,2,4,6$ in this order.

Deleting at most three vertices leaves the graph connected. In cyclic order, consecutive surviving vertices are joined unless separated by a run of at least two deleted vertices. Disconnection requires two distinct such runs, hence at least four deletions. Conversely deleting the four neighbours of a vertex isolates it, so the vertex connectivity is exactly four. Disjoint graph paths joining $0$ to $4$ and $2$ to $6$ cannot exist: both would lie in the closed disk complementary to the outer face, and their endpoints alternate on its boundary. A first such graph path is a crosscut of the disk; the Jordan curve theorem puts the other two endpoints on opposite sides, forcing the second graph path to meet it. ThusThis is a counterexample to the unrestricted implication; no claim that the same construction works for every $k$ is needed.

Couple the uniform random graph process by giving every possible edge an independent uniform label in $[0,1]$ and revealing them in increasing order. The graph at label threshold $p$ is a binomial random graph. Define ${\tau }_0$ as the first step with no isolated vertices and ${\tau }_c$ as the first connected graph. Deterministically ${\tau }_c\ge {\tau }_0$. We prove the reverse inequality with high probability by tracking the same process through a short interval.

Put $w=\frac{1}{4}\log \log n$, $p_{\pm }=(\log n\pm w)/n$, and $L=n{p}_{-}$. At $p_{-}$ the isolated vertex count $Z$ hasThe variance estimate follows by comparing two isolated-vertex indicators, whose joint-to-product probability ratio is $(1-p_{-}{)}^{-1}$. Thus $Z>0$ with high probability. Also the Markov inequality gives $Z\le \log n$ with probability tending to one.

At this same threshold, exclude every graph component with order $2\le s\le n/2$. For $2\le s\le n/\log n$, any such component contains a spanning tree. The Cayley formula and a union bound therefore giveIn this range the bracket is at most $A=e^{2}L{e}^w/n=o(1)$. Summing over $s\ge 2$ gives $O(n{A}^2/L)=O(L{e}^{2w}/n)=o(1)$. For $n/\log n<s\le n/2$, even the cut-absence bound is enough:The bracket tends to zero, so this range also has total probability $o(1)$. Consequently the graph at $p_{-}$ consists of one component of order greater than $n/2$ and its isolated-vertex set $S$, where $1\le |S|\le \log n$ with high probability.

Conditional on the entire graph at $p_{-}$, every unrevealed edge label remains independently uniform on $(p_{-},1)$. In particular,There are no isolated vertices at $p_{+}$ with high probability, because their expected value is asymptotic to $e^{-w}\to 0$. On the intersection of these events, each vertex of $S$ loses isolation by joining the original large component, never by forming a separate small component with another vertex of $S$. At every step between these two thresholds there is therefore one nontrivial component and some isolated vertices. The final isolated vertex disappears precisely when the graph becomes connected. This proves the connectivity hitting time equals disappearance of isolated vertices result:

For the critical-window probability, let $p=(\log n+\alpha (n))/n$ with $|\alpha (n)|\le B$. For each fixed $j$, the falling factorial moment of the isolated-vertex count isuniformly for such shifts. Apply the Bonferroni inequalities to the zero-count event. Its odd and even truncations bracket $\mathrm{Pr}(Z=0)$ by partial sums of ${\sum }_{j\ge 0}(-1{)}^j{e}^{-j\alpha (n)}/j!$. Since $e^{-\alpha (n)}\le e^B$, their remainders tend uniformly to zero. Hence $\mathrm{Pr}(Z=0)=e^{-e^{-\alpha (n)}}+o(1)$. The process equality just proved changes this probability by at most its $o(1)$ failure probability. ThereforeThe ratio follows because the denominator is bounded below by $e^{-e^B}>0$; no convergence of $\alpha (n)$ is needed.

The printed second conclusion has the complementary denominator and is false as written. For $\alpha (n)=0$, the printed ratio tends to $e^{-1}/(1-e^{-1})=1/(e-1)\ne 1$. Its denominator $1-e^{-e^{-\alpha (n)}}$ is correct for the probability of being disconnected. Thus either remove the leading $1-$ in the denominator or replace “connected” by “disconnected”; the proof supplies both corrected versions.

Orient each edge both ways. A unit flow $j$ from $x$ to $y$ is antisymmetric, $j(u,v)=-j(v,u)$, with divergence of a flow equal to $+1$ at $x$, $-1$ at $y$ and zero elsewhere. Its energy iswhere each unoriented edge is counted once. Put $c_e=1/r_e$. The electrical unit current is $i(u,v)=c_{uv}(V(u)-V(v))$, where the potential $V$ solves the Kirchhoff node law with those source and sink divergences. Because $G$ is a connected graph, this potential is unique up to an additive constant. The effective resistance is the electric potential difference needed for unit current,Discrete summation by parts gives ${\mathcal{E}}_r(i)={\sum }_{u}V(u)\mathrm{div}i(u)=R(x,y)$.

The Thomson principle says that this current minimizes energy among all unit flows. Indeed write any other unit flow as $j=i+k$, where $\mathrm{div}k=0$. ThenConsequentlyThis also proves uniqueness of the minimizing current.

If $r_e^{\prime }\ge r_e$ for every edge, then ${\mathcal{E}}_{r^{\prime }}(j)\ge {\mathcal{E}}_r(j)$ for every admissible flow. The admissible set is unchanged, so taking its minimum proves the Rayleigh monotonicity principle:Deletion is the limiting operation $r_e\to \infty$: finite-energy flows must then carry zero current on that edge. If the terminals become disconnected, the effective resistance is infinite.

Use $T_y=\inf \{n\ge 0:X_n=y\}$ and the positive return time $T_x^{+}=\inf \{n\ge 1:X_n=x\}$. The walk has transitions $p_{uv}=c_{uv}/d(u)$, $d(u)={\sum }_v{c}_{uv}$; its transition matrix defines a reversible Markov chain, although the transition probabilities need not be symmetric.

The voltage $h(u)=P_u(T_x<T_y)$ equals one at $x$, zero at $y$, and is a harmonic function on a graph away from the terminals: $h(u)={\sum }_v{p}_{uv}h(v)$. For this unit electric potential difference the electric current isThe first-step analysis therefore proves the return probability from effective resistance identity:Finite irreducibility ensures eventual hitting of one of the terminals, so no missing escape event appears in this finite-network calculation.

For an infinite locally finite connected graph, exhaust it by finite sets and wire their exteriors to one sink. The event of exiting before the first return decreases to the event of never returning. Thuswith $1/\infty =0$. In particular recurrence is equivalent to infinite effective resistance to infinity.

After deleting an edge, consider any infinite component and choose a root $o$ away from that edge's endpoints. Its vertex degree $d(o)$ is unchanged. On every finite wired exhaustion the Rayleigh monotonicity principle makes the resistance no smaller; the limit of a sequence does too. A recurrent original network consequently leaves a recurrent component. Finite components give recurrent walks as well, with an isolated graph vertex viewed as an absorbing state. This proves that edge deletion preserves recurrence. The phrase “no less recurrent” refers to this recurrence comparison: at a deleted-edge endpoint the vertex degree factor also changes, so monotonicity of its first-return probability alone should not be inferred.

First suppose $G$ is 3-connected and noncomplete, and write $\Delta =\Delta (G)$. There is an induced path $a,v,b$ with $a,b$ nonadjacent: otherwise the first three vertices of any shortest path between nonadjacent vertices would contradict that assertion. Since $G$ is 3-connected, $G-\{a,b\}$ is a connected graph. Choose a spanning tree of that graph rooted at $v$. Color $a,b$ first with the same color, then color the other vertices in reverse tree order, leaving $v$ last. Every vertex except $v$ has its tree parent uncolored and thus at most $\Delta -1$ previously colored neighbors. At $v$, the two neighbors $a,b$ share a color, so again at most $\Delta -1$ colors are forbidden. This constructs a proper $\Delta$-coloring and proves Brooks' bound for 3-connected noncomplete graphs. A complete graph is exactly the excluded case; a 3-connected graph cannot be an odd cycle.

For the partition claim, assume $d_1,d_2$ are nonnegative integers with $d_1+d_2=\Delta -1$. MinimizeIf a vertex in $V_1$ has internal degree $a\ge d_1+1$, its degree $b$ into $V_2$ is at most $d_2$. Moving it to $V_2$ changes $\Phi$ by $d_{1}b-d_{2}a\le -d_2$, contradicting minimality when $d_2>0$. The analogous move handles a violation in $V_2$ when $d_1>0$. For a zero coefficient, break ties among minimizers by minimizing the total number of internal edges. If $d_2=0<d_1$, minimality of $\Phi =d_{1}e(G[V_2])$ ensures $V_2$ is independent; a violating vertex in $V_1$ has all its $\Delta =d_1+1$ neighbors in $V_1$ and no neighbor in $V_2$, so moving it reduces the tie-break quantity without increasing $\Phi$. The reversed argument handles $d_1=0$. If both are zero then $\Delta =1$, and the graph is a union of isolated vertices and edges, admitting two independent parts. ThusFor $\Delta \ge 5$, put $d_1=3,d_2=\Delta -4$. A maximum-degree-three graph containing no $K_4$ is 3-colorable. Here is why the previously proved 3-connected case suffices: connected graphs of degree at most two are paths or cycles and use at most three colors. Split a larger graph at cut vertices and permute colors when gluing. In a 2-connected cubic graph with a two-vertex cut $\{u,v\}$, a cut edge $uv$ gives colorings of the sides glued with their distinct endpoint colors. If $u,v$ are nonadjacent, the cut components have positive numbers of edges to both endpoints and the total endpoint degrees are at most three. There are at most three components. With three components, adding $uv$ to each side preserves maximum degree three and gives the endpoints degree two. No new $K_4$ is created, so induction supplies side colorings with distinct endpoint colors, which can be permuted to agree. With two components, the components incident twice to $u$ and twice to $v$ either agree or differ. If they differ, adding $uv$ to each side preserves maximum degree three; each augmented side is smaller and cannot be $K_4$, because one endpoint then has degree only two, so induction gives distinct-endpoint colorings. If they agree, call the side with only one edge from each endpoint the small side. Any coloring of the other side can be matched on it: for equal endpoint colors, contract $u,v$ in the small side (the merged vertex has degree at most two); for distinct colors add $uv$ (the endpoints again have degree two). Induction applies in both cases. A 2-connected graph with no two-vertex cut is 3-connected and was handled above. This proves the needed subcubic coloring fact without quoting the unproved full theorem.

Use three colors on $V_1$ and at most $d_2+1=\Delta -3$ fresh colors on $V_2$, by greedy coloring. This gives $\chi (G)\le \Delta$. More usefully, repeatedly remove degree-at-most-three parts: the partition supplies a four-degree reduction for a cost of three colors. If $f(\Delta )=\frac{3}{4}\Delta +\frac{3}{2}$, then $3+f(\Delta -4)=f(\Delta )$. Induction in $\Delta$, with the remaining part still $K_4$-free, givesThe base cases $\Delta =0,1,2,3$ use respectively $1,2,3,3$ colors, within this bound; at $\Delta =4$, Brooks' theorem would give four, but the same partition with $(3,0)$ gives a 3-colorable part and an independent part, hence four. Thus the induction requires no unproved general Brooks theorem.

A connected graph with $n>1$ has no isolated vertices. Conversely, a disconnected graph with no isolated vertices has a connected component with size between $2$ and $n/2$. We must show that this latter event has probability tending to zero.

The permitted component-size estimate excludes sizes between $\log \log n$ and $n/2$ with high probability. For the remaining small sizes, let $C_k$ count components with $k$ vertices. A connected graph on a fixed $k$-vertex set contains a spanning tree. By the Cayley formula, there are $k^{k-2}$ labelled trees, as follows from the Prüfer code bijection between labelled trees and sequences of $k-2$ labels. A union bound over the trees, together with the absence of every edge to the complementary vertex set, givesPut $a=np=\log n+c$ and $L=\lceil \log \log n\rceil$. Using $\left(\genfrac{}{}{0ex}{}{n}{k}\right)\le (en/k{)}^k$ and $1-p\le e^{-p}$, uniformly for $2\le k\le L$ we obtainHere $p{L}^2\to 0$. Therefore, with ${\rho }_n=e^{1-c}a/n\to 0$,The Markov inequality excludes all these small components with high probability. Together with the permitted estimate, this proves that the difference between the probability of connectivity and the probability of no isolated vertices tends to zero. Hence

False. Attach 594 pendant vertices to one vertex of $K_{3,3}$. The connected graph still contains the nonplanar $K_{3,3}$, but has $v=600$, $e=603$, and average degree of a graph $2e/v=2.01$. Attaching more leaves lowers the average further toward two without making the graph planar.