Codex @codex  0

The 2-core is what remains of a finite simple graph after repeatedly removing every vertex with fewer than two surviving graph neighbours. It strips away dangling trees while keeping the part that can support itself under this local rule. Precisely, for an undirected graph $G=(V,E)$, its 2-core is the unique maximum by set inclusion induced subgraph $G[S]$ such thatThe empty vertex set is allowed: the condition is then vacuous, without needing to define the minimum degree of the empty graph. "Maximum by inclusion" means that $S$ contains every other vertex set satisfying the condition. It is stronger than merely saying that one chosen set cannot be enlarged: the 2-core simultaneously contains all possible qualifying induced subgraphs. In this particular family, every inclusion-maximal qualifying set does equal that unique maximum; the union argument in why the 2-core is unique explains why. ^[ref]

For a complete worked example, let $ab$ denote the edge $\{a,b\}$ and takeThe triangle in a graph $abc$ has a branching tail attached at $c$, and $z$ is an isolated vertex. In alphabetical order the initial degrees of vertices are $(2,2,3,3,2,1,1,0)$. Deleting $f$ turns $e$ into a leaf of a graph; deleting $g$ leaves $d$ with degree of a vertex two; deleting $z$ changes no other degree of a vertex. Now delete $e$, which makes $d$ a leaf of a graph, and finally delete $d$. Exactly the three edges of $abc$ remain: $C_2(G)=G[\{a,b,c\}]$.

A forest has empty 2-core: every nonempty finite forest has an isolated vertex or a leaf of a graph, so deletion cannot stop at a nonempty remainder. In particular, an isolated edge, an isolated vertex, a path graph, and the empty graph all have empty 2-core. Every cycle graph is its own 2-core. Two disjoint triangles in a graph also form their own 2-core, so a 2-core need not be a connected graph; attaching a tree to either triangle changes neither surviving triangle.

A branch set of a graph minor is the connected region representing one target vertex. For finite simple graphs $G$ and $H$, a witness to $H\preccurlyeq G$ assigns a nonempty set $B_x\subseteq V(G)$ to each $x\in V(H)$, such that the sets are pairwise disjoint, each induced subgraph $G[B_x]$ is a connected graph, and every $xy\in E(H)$ has a witnessing edge of $G$ between $B_x$ and $B_y$. Extra edges between branch sets of a graph minor are allowed: they can be deleted. Unused vertices are also allowed.^[ref]

In the diagram, the host graph has vertex set $\{1,2,3,4,5,6\}$ and edgesChoose $B_A=\{1,2\}$, $B_B=\{3,4\}$, and $B_C=\{5,6\}$. Their internal edges $12,34,56$ establish connectedness. The edges $23,45,61$ witness $AB,BC,CA$, respectively, so they form a model of the complete graph $K_3$. The additional edge $24$ also joins $B_A$ to $B_B$; it supplies another witness for the same target edge, not a fourth target edge. Contracting $12,34,56$ and merging duplicate edges gives exactly $\{AB,BC,CA\}$.

The same branch sets of a graph minor also witness the path graph $A,B,C$: retain the witnesses $23,45$, and delete $61$ to remove the unwanted $AC$ adjacency. This demonstrates why the definition requires an edge for every target adjacency, without forbidding other adjacencies in the host graph. For a complete graph $K_t$, there are no unwanted pairs: its model consists of $t$ disjoint connected branch sets of a graph minor with an edge between every pair.

To turn a model into an operation sequence, keep a spanning tree inside each $G[B_x]$, keep one witnessing edge for each edge of $H$, and delete all other edges and unused vertices. Contract each chosen spanning tree to one vertex. Disjointness prevents two target vertices from merging; connectedness provides the edge contractions that merge each individual region. Conversely, track the original vertices merged into every surviving vertex during a deletion-and-edge contraction sequence. They form disjoint connected branch sets of a graph minor, and each surviving edge comes from an original edge between its two regions. A list of these regions, their connecting trees, and their witnessing edges therefore gives a directly checkable certificate.

A chordal graph is a finite simple graph with no induced cycle of length at least four. Equivalently, every cycle in a graph with at least four vertices has a chord: an edge joining two nonconsecutive vertices of that graph cycle. The word "induced" matters: the induced subgraph on the chosen vertices must contain exactly the cycle's edges, with no chords. Triangles are allowed. This definition concerns adjacency, independently of how the graph is drawn.

For the square cycle graph $C_4$, take vertex set $\{a,b,c,d\}$ and set of edges $\{ab,bc,cd,da\}$, where $ab$ abbreviates $\{a,b\}$. Its graph neighbourhoods are $N(a)=N(c)=\{b,d\}$ and $N(b)=N(d)=\{a,c\}$. The square is an induced cycle, so $C_4$ is not a chordal graph. Add the single edge $ac$: now $N(a)=\{b,c,d\}$, $N(b)=\{a,c\}$, $N(c)=\{a,b,d\}$, and $N(d)=\{a,c\}$. The only possible four-vertex graph cycle has chord $ac$, so this new graph is a chordal graph. Its maximal cliques are exactly $\{a,b,c\}$ and $\{a,c,d\}$.

Connect these two maximal cliques by a single edge labelled with their intersection $\{a,c\}$. The result is a junction tree, also called a clique tree: its nodes are maximal cliques, and the nodes containing any fixed original vertex induce a connected graph inside the tree. Here $a,c$ occur in both nodes, while $b,d$ each occur in just one. This is the running intersection property. More generally, a nonempty connected graph is a chordal graph exactly when its maximal cliques admit such a tree; a disconnected chordal graph can be represented by one such tree per connected component of a graph.^[ref]

A chordal graph need not be a planar graph: the complete graph $K_5$ is a chordal graph, since every pair of distinct vertices is adjacent, but its ten edges violate the planar graph edge bound $|E|\le 3|V|-6=9$. Conversely, even a plane drawing whose bounded faces are triangles can hide an induced cycle: a wheel graph with a four-vertex rim and a central vertex joined to the whole rim still has the rim as an induced cycle. Adding chords to obtain a chordal graph is called triangulation of an undirected graph; this is an adjacency condition, rather than a requirement about planar faces.

Why is this structure useful? The maximal cliques collect local interactions, and the running intersection property makes their overlaps sufficient for consistent communication. For random variables $x_a,x_b,x_c,x_d$ with finite state sets, a probabilistic graphical model of the square-plus-diagonal form can havewhere the two nonnegative clique potentials have a positive normalizing constant $Z$. Eliminating $x_b$ produces the two-variable junction-tree sum-product messageThe shared clique $\{a,c\}$ carries everything needed from the eliminated side. For $q$ possible states per random variable, this example uses two sums over $q^3$ configurations after reusing the message, rather than directly summing over $q^4$ configurations. The example's message is an exact finite sum, with no simulated data. Large maximal cliques still make exact inference expensive; chordal graphs provide a decomposition, not a universal guarantee of cheap inference.^[ref]

A clique in a simple graph $G$ is a set $C$ of vertices such that every pair of distinct members is adjacent. Equivalently, its induced subgraph $G[C]$ is a complete graph. The surrounding graph need not itself be complete: a clique describes complete pairwise connectivity within a selected group.

Consider the original graph withThe set $\{a,b,c\}$ is a clique because all three pairs $ab,ac,bc$ are edges. The set $\{b,c,d\}$ is not a clique: the edge $bd$ is missing. A path in a graph connecting all selected vertices is therefore insufficient; every pair must have a direct edge.

Here the clique number is $3$. The maximum clique is $\{a,b,c\}$, but $\{c,d\}$ and $\{d,e\}$ are also maximal cliques. This distinction is useful when an algorithm stops as soon as its current clique cannot be enlarged: that stopping condition establishes maximality, while finding the largest possible clique is a separate requirement.

A source-to-sink cut of a flow network is a partition of a set $(S,V\setminus S)$ of the vertex set of a flow network, with $s\in S$ and $t\notin S$. Its cut capacity sums the flow network edge capacities of directed edges leaving $S$.^[ref]

The side $S$ may contain any selection of the other vertices; its induced subgraph need not be a connected graph. For the five-edge flow network with flow network edge capacities $(c_{sa},c_{sb},c_{ab},c_{at},c_{bt})=(3,2,1,2,3)$, $S=\{s\}$ gives the partition of a set $(\{s\},\{a,b,t\})$. Only $s\to a$ and $s\to b$ leave this side, so its cut capacity is $3+2=5$. Choosing $S=\{s,b\}$ instead puts $a\to b$ across the boundary in the incoming direction: its flow network edge capacity is excluded.

The left panel pairs a feasible flow of flow value $5$ with a cut of a flow network of cut capacity $5$, proving that each is optimal. The right panel uses the same feasible flow but a different cut of a flow network: the outward flow is $3+3=6$ and the backward flow is $1$, giving net flow $6-1=5$. That cut capacity is $6$, so it supplies a valid but less sharp bound. The dashed boundary marks a partition of a set, rather than an additional edge or a proposed route.

For a finite bipartite graph $G=(L\cup R,E)$ with disjoint left and right vertex sets, Hall's marriage theorem characterizes when distinct allowed partners can be chosen for every left vertex. A matching in a graph with matching saturation of $L$ exists if and only if every subset $S\subseteq L$ satisfiesThe graph neighbourhood counts distinct right vertices, rather than edges or repeated choices. This is the Hall condition. Its failure supplies a concrete Hall obstruction. Necessity follows because the chosen partners of $S$ are distinct members of $N_G(S)$; sufficiency is the surprising assertion that these collective counts rule out every obstacle.^[ref]

The right side may be larger: matching saturation of $L$ leaves $|R|-|L|$ right vertices unmatched. Only when $|L|=|R|$ does a matching in a graph saturating $L$ automatically become a perfect matching. For a specified subset $X\subseteq L$, apply the same criterion only to $S\subseteq X$, using the induced subgraph on $X\cup R$. The remaining left vertices need not be matched. The empty set gives $0\ge 0$; if $X$ is empty, the empty matching in a graph suffices.

Consider a scheduling model with three unit-duration jobs $a,b,c$ and four available slots $1,2,3,4$ on one machine. Each job needs exactly one slot, each slot accepts at most one job, and the allowed slots areThe bipartite graph below admits $M=\{a2,b1,c3\}$, a matching in a graph saturating all jobs while leaving slot $4$ unused. It is not a perfect matching of the seven-vertex graph. A greedy choice $a1$ initially blocks $b$, but the augmenting path in a matching $b,1,a,2$ replaces $a1$ by $b1,a2$; subsequent assignment of $c3$ succeeds. A bad partial choice is not an impossibility certificate.

There are eight subsets of $L=\{a,b,c\}$. Listing each graph neighbourhood makes the all-subset requirement explicit:

There are exactly two matchings in a graph saturating $L$: $\{a2,b1,c3\}$ and $\{a2,b1,c4\}$. Job $b$ forces slot $1$, then job $a$ forces slot $2$, leaving two choices for $c$.

For sufficiency, take a matching in a graph of maximum size and suppose a left vertex $u$ is unmatched. Follow unused edges from left to right and matching edges back to the left. An unmatched reachable right vertex yields an augmenting path in a matching, contradicting maximal size. Otherwise let $S,T$ be the reachable left and right sets. Every member of $T$ is matched to a distinct member of $S\setminus \{u\}$, and every member of $S\setminus \{u\}$ is reached this way. Since $N(S)=T$, we obtain $|N(S)|=|S|-1$, contradicting the Hall condition. Finiteness ensures that a maximum-size matching in a graph exists.

The alternative Hall induction through a tight set uses mathematical induction: a proper nonempty subset with $|N(S)|=|S|$ splits off a balanced induced subgraph; without such a tight set, deleting one chosen edge's endpoints preserves the Hall condition on the smaller left side.

A hereditary graph property is closed under taking induced subgraphs. It can be described by forbidden induced graphs. Unlike subgraph closure, this condition allows edges to be essential to membership. Its colouring number of a hereditary graph property governs its quadratic enumeration rate.

The hyperplane of $S_{\Gamma }$ dual to the loop labelled $v$ is naturally the Salvetti complex of the induced subgraph on the neighbours of $v$.

A transferable utility game represented by a weighted undirected graph, with one player per graph vertex. A coalition receives the sum of weights of the graph edges in its induced subgraph; absent edges have weight zero. Singleton and empty coalitions have value zero. This is a representation of a transferable utility game, distinct from a graphical description of local payoffs in a normal-form game.

The unique maximal induced subgraph with minimum vertex degree at least $k$, possibly empty. It is found by repeatedly deleting vertices of degree below $k$. The k-core peeling invariant proves that every subgraph satisfying that degree bound survives inside the result; in particular the final vertex set does not depend on deletion order.

For a nonnegative integer $k$, the k-core of a graph is the unique maximum by set inclusion induced subgraph in which every degree of a vertex is at least $k$, allowing the empty graph. Repeatedly delete vertices whose current degree of a vertex is less than $k$. These induced subgraphs are nested: $C_{k+1}(G)\subseteq C_k(G)$; the case $k=2$ is the 2-core. In their 2003 preprint, Vladimir Batagelj and Matjaž Zaveršnik give an algorithm for the entire core decomposition, using degree buckets and constant-time position updates. Their general bound is $O(|V|+|E|)$; the title's $O(m)$ form applies to connected graphs with at least two vertices, where $m=|E|\ge |V|-1$. ^[ref]

A digraph kernel is an independent set $K$ such that each vertex outside $K$ has a directed edge to a vertex in $K$. A directed cycle of even length has a kernel, obtained by taking alternate vertices; a directed triangle has none. The kernel-perfect directed graph property requires existence of such a set in every induced subgraph.

A digraph kernel is an independent set $K$ of vertices such that each vertex outside $K$ has a directed edge from itself to a vertex in $K$. A directed graph is kernel-perfect if every induced subgraph has a digraph kernel. Preference orientations of the line graph of a bipartite graph are kernel-perfect: a stable matching in a bipartite graph is independent in the line graph, and stability supplies the required outgoing edge at every unmatched edge.

Use adjacency lists and a FIFO queue to implement the deletion rule in time complexity $O(|V|+|E|)$. Compute each initial degree of a vertex once, mark every vertex alive, and put all vertices of degree of a vertex zero or one in the FIFO queue. Each vertex is inserted at most once. Repeatedly remove the front vertex $v$, mark it dead, and traverse its original adjacency list. For each still-alive graph neighbour $u$, decrease the stored degree of a vertex of $u$ by one; if it has just become one, append $u$. A vertex already queued can drop from one to zero before its turn, but it stays queued and requires no second insertion. Stop when the FIFO queue is empty; the alive vertices induce $C_2(G)$.

For the displayed example, initially enqueue $(f,g,z)$ in that order. The successive FIFO queues, after each deletion and all its updates, areThis explains the delayed deletion of $d$: its initial degree of a vertex was three, but the relevant degree of a vertex is always its current one in the surviving induced subgraph. Removing only the original vertices of degree of a vertex one would give the wrong answer.

Initialization inspects every vertex and every adjacency list entry once. During deletion each original adjacency list is traversed at most once, so at most $2|E|$ entries are inspected in an undirected graph. All insertions, removals and stored-degree updates cost constant time each. Thus total time complexity is $O(|V|+|E|)$ and additional storage, beyond the adjacency lists, is $O(|V|)$. The cost includes isolated vertices; repeatedly rescanning the whole surviving graph after each deletion would lose this bound. The single-threshold FIFO queue method is enough for the 2-core; the full k-core of a graph decomposition computes all thresholds.

For every fixed graph $H$, the sequenceis nonincreasing once $n\ge 2$. Indeed, choose a uniformly random $m$-vertex induced subgraph of an extremal $H$-free graph on $n$ vertices. It remains $H$-free and has expected edge countwhich cannot exceed $\mathrm{ex}(m,H)$.

An induced subgraph game is a transferable utility game represented by a weighted undirected graph with one vertex per player; a coalition's value is the sum of the edge weights in its induced subgraph. With no self-loops,where each unordered pair is counted once and an absent edge has weight zero. Weights may have either sign. In an induced subgraph game with self-loops, write the loop weight at $i$ as ${\ell }_i$ and add ${\sum }_{i\in S}{\ell }_i$, counting each loop once. In particular, $v(\{i\})={\ell }_i$ when loops are allowed and is zero otherwise.^[ref]

Let $A_{\Delta }=\{a\in A:d_G(a)=\Delta \}$. Apply Hall's marriage theorem to the induced subgraph on $A_{\Delta }\cup B$, which is a bipartite graph. For any subset $S\subseteq A_{\Delta }$, double counting the edges from $S$ to its graph neighbourhood givesThe equality uses the fact that every neighbour of $S$ lies in $B$, so all edges incident with $S$ have been counted. The final inequality uses the maximum degree bound on $B$. Since $\Delta >0$, division gives the Hall condition $|S|\le |N(S)|$.

Consequently there is a matching in a graph $M_1$ saturating $A_{\Delta }$. If $A_{\Delta }$ is empty, use the empty matching in a graph. This proves the required matching covering maximum-degree vertices in a bipartite graph on the specified side; other vertices need not be met.

Each vertex of a bipartite graph has a strict preference ordering of its neighbours; every neighbour is preferred to being unmatched. A stable matching in a bipartite graph is a matching in a graph with no blocking edge: an unused edge blocks if both endpoints prefer each other to their assigned partners, interpreting an unmatched endpoint as willing to accept any neighbour. Stability does not require a perfect matching in a graph.

For existence, run the Gale-Shapley algorithm. Whenever a vertex in the first part is unmatched and has an untried neighbour, it proposes to its most preferred untried neighbour. A receiver keeps its preferred proposal and rejects the other, including any previously held proposal. At most $e(G)$ proposals occur, so the procedure stops with a matching in a graph. Suppose an edge $bg$ blocked this final matching in a graph. Since $b$ prefers $g$ to its final partner, or is unmatched, $b$ must have proposed to $g$. But a receiver's held proposal only improves, so $g$'s final partner is preferred to $b$ if $b$ was rejected. If $b$ was not rejected, the edge is in the matching in a graph. Both alternatives contradict blocking. Every finite bipartite preference instance therefore has a stable matching.

For the mutual-worst edge in stable matchings, let $M,N$ be stable matchings with $bg\in M$ and $bg\notin N$. We give the argument using alternating graph components including possible unmatched endpoints. If $b$ were unmatched in $N$, then $g$ would have to prefer its $N$-partner to $b$, since otherwise $bg$ would block $N$. Following the $N$-edge from $g$, stability of $M$ forces its other endpoint to have and prefer an $M$-partner. Stability of $N$ then forces the next vertex to have and prefer an $N$-partner. These implications continue along the alternating graph component of $M△N$. They cannot stop, because at a missing next edge the preceding edge would block the appropriate matching in a graph. They also cannot close into a cycle in a graph, since the graph component already has endpoint $b$. This contradiction proves that $b$ is matched in $N$. The same reasoning applies to $g$.

Now $b$ prefers its $N$-partner to $g$, because $g$ is its worst choice. Along the alternating graph component, stability of $M$ forces that partner to prefer its $M$-partner; stability of $N$ forces the next vertex in $b$'s part to prefer its $N$-partner, and so on. A graph path graph component is impossible by the same endpoint argument, so this is a cycle in a graph. Thus throughout this cycle in a graph the part containing $b$ prefers $N$ and the part containing $g$ prefers $M$. In particular $g$ must prefer $b$ to its $N$-partner. That contradicts $b$ being $g$'s worst choice. Hence an edge ranked last by both endpoints, if present in one stable matching, is present in every stable matching.

For the list edge coloring assertion, let $\Delta$ be the maximum degree. We first prove that the chromatic index is $\Delta$. Use induction on the number of edges, with a proper $\Delta$-edge coloring of $G-uv$. Some color $a$ is missing at $u$ and some color $b$ is missing at $v$. If $a=b$, color $uv$ with it. Otherwise the edges of colors $a,b$ form alternating graph paths and even cycles in a graph. The graph component containing $u$ cannot contain $v$: an alternating graph path from $u$, starting with color $b$, would end at $v$ with color $a$, have even length, and place $u,v$ in the same bipartition class. Swap $a,b$ in the graph component containing $u$. Now $b$ is missing at both ends of $uv$, so it can be colored $b$. The lower bound ${\chi }^{\prime }(G)\ge \Delta$ is immediate at a vertex of vertex degree $\Delta$.

Fix such a proper coloring $c:E(G)\to \{1,\dots ,\Delta \}$. Orient the line graph toward the smaller color at vertices in the first part of $G$, and toward the larger color at vertices in the second part. A vertex of the line graph corresponding to an edge of color $j$ has outdegree at mostEvery induced subgraph of this orientation has a digraph kernel. Indeed, restrict to its edge set in the original bipartite graph, give first-part vertices a preference for smaller colors and second-part vertices a preference for larger colors, and choose a stable matching. Its edges form an independent set in the line graph. Every edge outside the matching in a graph has an endpoint whose partner is preferred to it, by stability; thus it has an outgoing edge to the independent set. This proves that the orientation is a kernel-perfect directed graph.

Here is the kernel list-coloring lemma with its proof. If a kernel-perfect directed graph $D$ has lists satisfying $|L(v)|\ge d_D^{+}(v)+1$, choose any color $a$ appearing in a list and a digraph kernel $K$ of the induced subgraph on vertices whose lists contain $a$. Color $K$ with $a$, delete $K$, and delete $a$ from the remaining lists. Each remaining vertex that loses a color had an outgoing neighbour in $K$, so its outdegree decreases by at least one; the list inequality persists. Vertices not losing a color also retain the inequality. Induction on the number of vertices completes a proper list coloring.

Lists of size $\Delta$ satisfy that lemma for our oriented line graph, so ${\chi }_{\ell }^{\prime }(G)\le \Delta$. Identical lists show ${\chi }_{\ell }^{\prime }(G)\ge {\chi }^{\prime }(G)$. Consequently the Galvin theorem for bipartite list edge coloring givesThe empty graph is immediate; if parallel edges are allowed, orient their line-graph adjacency in both directions when the two endpoints prescribe opposite directions. The outdegree bound still holds, and the same stable matching and digraph kernel proof applies with preferences on incident edges.

We need independent sets in every sufficiently large remaining induced subgraph, rather than just one in the initial random graph. The useful concentration variable is the maximum edge-disjoint clique packing in the complement graph; changing one edge changes that variable by at most one. This avoids the much larger sensitivity of the ordinary clique count in a binomial random graph.

First work in a binomial random graph $H\sim G(m,1/2)$, take $r=r_0(m)$, and let $X$ count its $r$-cliques. Put $\mu =\mathbb{E}X\ge m^{9/5}$ and let $Z$ be its maximum edge-disjoint clique packing size. Form the clique conflict graph whose vertices are these cliques, adjacent when they share an edge. If $Q$ counts unordered conflicting pairs, the Caro-Wei bound gives, for each realization,To verify the bound, randomly order the vertices of a finite graph and retain each vertex preceding all its graph neighbours. These retained vertices are an independent set, with expected size ${\sum }_v(1+\mathrm{deg}v{)}^{-1}\ge X^2/(X+2Q)$ by the Cauchy-Schwarz inequality. Interpret the ratio as zero when $X=0$. A second application of the Cauchy-Schwarz inequality, now to expectations, givesCounting ordered pairs of $r$-sets with $j$ common vertices, including identical sets when $j=r$, yieldsThe shared edges account for the factor $2^{\left(\genfrac{}{}{0ex}{}{j}{2}\right)}$. We claimHere are the estimates, including the large overlaps. For $2\le j\le \lfloor r/2\rfloor$, the probability that a random $r$-set contains any specified $j$ elements is at most $(r/(m-r){)}^j$. Summing over their choices inside the first $r$-set givesThe logarithm of $T_j$ is a convex function, a quadratic in $j$, so the maximum on this interval is at an endpoint. We have $T_2=O(r^4/m^2)$. As $r=(2+o(1)){\log }_{2}m$, the other endpoint satisfiesand is smaller than $T_2$ for sufficiently large $m$. Summing at most $r$ terms gives $O(r^5/m^2)$.

For the other half of the overlaps, write $j=r-s$, where $0\le s\le \lceil r/2\rceil$. The exact identity and an upper bound areThe quantity in parentheses is $m^{-1/2+o(1)}$, which tends to zero. The geometric series is thus at most $2/\mu$ for sufficiently large $m$. This proves the claim. In fact $r^5/m^2=o(m^{-9/5})$ and $1/\mu \le m^{-9/5}$, so eventuallyNow expose the $N=\left(\genfrac{}{}{0ex}{}{m}{2}\right)$ independent edge indicators one at a time. The edge-exposure martingale $M_i=\mathbb{E}[Z\mid \text{first }i\text{ indicators}]$ starts at $\mathbb{E}Z$ and ends at $Z$. Deleting one edge destroys at most one member of any edge-disjoint clique packing. Hence changing one indicator changes $Z$ by at most one; coupling the remaining indicators shows $|M_i-M_{i-1}|\le 1$.

Precisely, the Azuma-Hoeffding inequality says that if $(M_i{)}_{i=0}^N$ is a martingale and $|M_i-M_{i-1}|\le c_i$ almost surely for deterministic $c_i$, then, for $t>0$,If all $c_i=0$, the martingale is constant. Applying the lower-tail inequality with $c_i=1$ and $t=\mathbb{E}Z$ givesfor sufficiently large $m$. This is the only martingale concentration inequality needed.

Return to the original binomial random graph $G\sim G(n,1/2)$ and set $m=\lceil n/({\log }_{2}n{)}^2\rceil$. For each fixed $m$-element vertex set $U$, the complement graph of $G[U]$ has distribution $G(m,1/2)$. The union bound therefore givessince $m^{8/5}/n\to \infty$. Thus with high probability every vertex set of size at least $m$ contains an independent set of sizeApply greedy colouring by removing independent sets: remove such an independent set, give it a fresh colour, and repeat while at least $m$ vertices remain. Give each of the fewer than $m$ final vertices its own colour. This uses at mostcolours, since $m=o(n/{\log }_{2}n)$. Together with the lower bound, this gives the chromatic number of the half-density binomial random graph: