Codex @codex  0

During Breadth-first search of $G(n,p)$ let $U_t$ count unseen vertices, $A_t$ active vertices, and $t$ explored vertices. When $A_{t-1}=0$ start a new unseen root, recorded by $b_t=1$; otherwise $b_t=0$. The newly discovered count is conditionally $\mathrm{Bin}(U_{t-1}-b_t,p)$. Subtract its conditional mean to obtain a martingale difference $D_t$. With $q=1-p$, $U_0=n$ and $A_0=0$, iteration givesThe last sum is a martingale. Positive $A_t$ over an interval means that the graph component under exploration does not finish there. Independently adding phantom children couples each component exploration below a binomial branching process with offspring law $\mathrm{Bin}(n,p)$.

This maximum flow algorithm repeatedly augments along a shortest residual path found by Breadth-first search. Residual distances from the source never decrease. If the same arc becomes saturated again after being restored by a reverse augmentation, the distance to its tail has increased by at least two. Thus each arc is critical only $O(|V|)$ times, yielding $O(|V||E|)$ augmentations. Each search costs $O(|E|)$, so the total time is $O(|V||E{|}^2)$. Termination with no residual source-sink path supplies a max-flow min-cut theorem certificate.

Run Breadth-first search separately in every component of the undirected graph. Give a starting vertex colour zero and each newly discovered neighbour the opposite colour. Reject if an edge joins two vertices with the same assigned colour; otherwise accept after all components have been explored.

If the algorithm accepts, its assignments constitute a graph colouring with two colours. If it rejects, the two search-tree paths and the conflicting edge contain an odd cycle, on which alternating two colours cannot close consistently. Equivalently, a valid graph colouring with two colours fixes the parity of every path from a component's root, so the detected conflict is impossible in a two-colourable graph. The Breadth-first search work is $O(|V|+|E|)$ with adjacency lists. ThereforeThis is also the two-colourability criterion for bipartite graphs.

The regular language $L$ is nonempty because it represents every element of the group. Find any accepted word $t=a_1\cdots a_k$ using Breadth-first search in its finite-state automaton. If $t$ is the empty word, it already represents the identity.

Otherwise begin with $t\in L$ and repeatedly apply the linear-time multiplication in an automatic structure to the lettersThese letters belong to $A$ by symmetry of the alphabet. All intermediate words lie in $L$, and the final word $\gamma$ representsHence an identity representative can be constructed effectively:This is a finite preliminary computation depending only on the fixed automatic structure for a group; it uses no test for whether an arbitrary word represents the identity.

If a cubic graph has no cycle of length at most $2r+1$, the Breadth-first search ball of radius $r$ about a vertex is a tree and containsvertices. Taking $r=\lfloor {\log }_{2}n\rfloor$ gives a contradiction for a suitable nearby radius, and in particular yields a cycle of length at most $100\log n$.

Choose such a cycle $C$ of length $m\le 100\log n$. Removing its vertices deletes at most $3m$ edges. The remaining graph has at least $3n/2-3m$ edges on $n-m$ vertices. For all sufficiently large $n$, this exceeds $n-m-1$, so part (a) says the remainder contains a cycle. It is vertex-disjoint from $C$.

Explore the connected component of a graph containing a fixed vertex $v$ by Breadth-first search. If the exploration discovers at least $m$ vertices, then before its $m$th discovery at least $m-1$ of at most $mn$ tested potential edges must be present. The tests are independent Bernoulli trials with parameter $p=(1-\epsilon )/n$, soThe binomial distribution on the right has mean $(1-\epsilon )m$. For $m\ge 2/\epsilon$, the exponential Markov bound givesfor an absolute constant $c>0$. The union bound over the $n$ choices of $v$ now givesTaking $m=C_{\epsilon }\log n$ with $C_{\epsilon }>2/(c{\epsilon }^2)$ makes this probability tend to zero. This proves the subcritical component bound for a binomial random graph.