If the intervals $J_k$ cover $A$, their translates $J_k+a$ cover $A+a$ and have the same lengths. Every candidate total length in the definition of $m^{\ast }(A)$ is therefore also a candidate for $m^{\ast }(A+a)$. Taking infima gives $m^{\ast }(A+a)\le m^{\ast }(A)$. Apply the same argument to $A+a$ and the translation $-a$ to obtain the reverse inequality. HenceThis translation invariance of Lebesgue outer measure holds for every subset $A$, including non-measurable sets and sets of infinite outer measure.

If ${\sum }_n{m}^{\ast }(A_n)=\infty$, the required inequality is automatic. Otherwise each $A_n$ has finite Lebesgue outer measure. Fix $\epsilon >0$. By the defining infimum, for each $n\ge 1$ choose a countable interval cover $\{J_{n,k}:k\ge 1\}$ withThe family indexed by $(n,k)\in {\mathbb{N}}^2$ is countable and covers ${\bigcup }_n{A}_n$. Since all lengths are nonnegative, its total length is at most ${\sum }_n{m}^{\ast }(A_n)+\epsilon$. Taking the infimum over covers of the union and then letting $\epsilon \downarrow 0$ givesThis proves countable subadditivity of Lebesgue outer measure directly from interval covers, without assuming that any $A_n$ is measurable.

Define the joint function by an unambiguous piecewise prescription:It is nonnegative and Lebesgue measurable: on the open triangle the power factor is continuous and $f(y)$ is measurable for the product sigma-algebra, and the zero extension is measurable. This also resolves the diagonal singularity and avoids evaluating a noninteger power of a negative number outside the triangle. The source's inclusion of $y=x$ in its indicator set changes only a null set; set the value there to zero.

The function $g(x)={\int }_0^{1}H(x,y)dy$ is measurable by Tonelli's theorem. Apply that theorem to exchange the nonnegative integrals, with infinity allowed until the estimate proves otherwise:The inner integral is $(1-y{)}^{\beta }/\beta$ because $\beta >0$. The weight is at most one because $0<y<1$. Since $g\ge 0$, this provesIn particular $g$ is finite almost everywhere; any exceptional infinite values may be replaced by zero to obtain an everywhere finite representative. This is the L1 bound for a Volterra power-kernel integral.

An everywhere-finite conclusion would be stronger and can fail when $0<\beta <1$, even for integrable $f$. For example, put $x_0=1/2$ and $\gamma =(1+\beta )/2$, and take $f(y)=(x_0-y{)}^{-\gamma }$ for $0<y<x_0$ and zero otherwise. Since $\gamma <1$, $f$ is integrable. Butbecause $\beta -1-\gamma =(\beta -3)/2<-1$. This does not contradict Lebesgue integrability, which requires finiteness only almost everywhere.

Fix $0<x<1$. On the open interval $(0,x)$, the function $y\mapsto (x-y{)}^{\beta -1}$ is finite, positive and continuous, and $f$ is nonnegative and Lebesgue measurable. Their product is therefore a nonnegative measurable function. Its Lebesgue integral is always defined as an element of $[0,\infty ]$, with no possibility of cancellation of two infinities. Thus $g(x)$ is well defined as a nonnegative extended integral.

The endpoint $y=x$ need not receive its formal power value: for $\beta <1$ that value would be singular. The integral is over $(0,x)$, and any chosen value at the endpoints has no effect because endpoints form a null set.

Finiteness is not implied by the present assumptions. For example, $f(y)=1/y$ is an admissible nonnegative measurable function. For any fixed $x$, the factor $(x-y{)}^{\beta -1}$ is bounded below by a positive constant on $0<y<x/2$, so $g(x)\ge C_x{\int }_0^{x/2}dy/y=\infty$. The later L1 norm bound will establish finiteness almost everywhere when $f$ is integrable. The construction is a Volterra power-kernel integral.

We prove the required differentiation under the integral sign directly. Fix $t_0>0$, and take a compact parameter interval $J\subseteq [0,\infty )$ containing $t_0$ in its interior. The jointly continuous partial derivative ${\partial }_{t}f$ is bounded on the compact rectangle $J\times [0,1]$ by some $M_1$.

For nonzero $h$ sufficiently close to zero, defineFor each $x$, the mean value theorem in the parameter gives $|D_h(x)|\le M_1$. The definition of the partial derivative also gives $D_h(x)\to {\partial }_{t}f(t_0,x)$. Since $M_1$ is integrable on $[0,1]$, dominated convergence applied along any sequence $h_n\to 0$ yieldsThusAt $t=0$, repeat the argument on $J=[0,\delta ]$ with $h>0$. It proves that the right derivative exists and satisfies the same formula at zero. This is the appropriate meaning of differentiability on the closed half-line. In fact $F^{\prime }$ is continuous there: apply part (i) to the continuous function ${\partial }_{t}f$.

The proof establishes differentiation of parameter integrals on compact rectangles under the exact regularity assumptions used here. In particular, it supplies the theorem's proof instead of assuming an interchange of a limit and an integral.

Fix $t_0\ge 0$. On a compact parameter interval containing all nonnegative $t$ sufficiently close to $t_0$, the corresponding rectangle with $x\in [0,1]$ is compact. The continuous function $f$ is therefore bounded there by some $M<\infty$, by the extreme value theorem.

For any sequence $t_n\ge 0$ tending to $t_0$, all sufficiently late $t_n$ lie in this rectangle's parameter range. For each $x\in [0,1]$, continuity givesThe constant function $M$ is integrable on $[0,1]$. The dominated convergence theorem therefore givesThe sequential criterion for continuity on a real interval proves $F$ is continuous on $[0,\infty )$. At zero this is right-continuity. This is continuity of parameter integrals on compact rectangles; the bound is local in the parameter, so $f$ need not be bounded on the entire unbounded strip.

Part (ii) shows that $\chi (G)\le \lambda (D)$ for every acyclic orientation $D$, so $\chi (G)$ is at most their minimum. Part (i), applied to an optimal colouring, supplies an acyclic orientation with $\lambda (D)\le \chi (G)$. Combining the inequalities givesThe parameter counts vertices on a graph path; if graph path length were instead counted in edges, the corresponding minimum would be $\chi (G)-1$.

These constructions prove chromatic number from acyclic longest paths.

For each vertex $v$, let $c(v)$ be the maximum number of vertices in a directed path ending at $v$. These numbers lie between one and $\ell$.

If $u\to v$ is an edge, a longest graph path ending at $u$ cannot already contain $v$, since that would give a directed cycle on appending $u\to v$. Appending it therefore creates a graph path ending at $v$, so $c(v)\ge c(u)+1$. Adjacent vertices consequently receive different colours. HenceAcyclicity is exactly what justifies extending the graph path without repeating a vertex.

Take a proper colouring $c:V(G)\to \{1,\dots ,k\}$ and orient every edge from its lower-coloured endpoint towards its higher-coloured endpoint. Along a directed path the colour strictly increases, so such a graph path has at most $k$ vertices. A directed cycle is impossible for the same reason. Thus

Write $\Delta =\Delta (G)$, which is at least two because $x$ has the two specified neighbours. Give $y$ and $z$ the same colour, say colour one; this is proper because they are nonadjacent.

Apply part (i) to the connected graph $G\setminus \{y,z\}$, with $x$ last. Colour its vertices greedily in the resulting order using a palette of $\Delta$ colours. Every vertex before $x$ has a neighbour later in this order, so at most $\mathrm{deg}(v)-1\le \Delta -1$ of its neighbours have already received colours. At least one palette colour is available.

When $x$ is reached, all its neighbours are coloured, but the two neighbours $y,z$ have the same colour. Thus there are at most $\mathrm{deg}(x)-1\le \Delta -1$ distinct forbidden colours. Colour $x$ with a remaining one. This constructs a proper colouring withThe common colour on the two initial vertices replaces the usual need for an uncoloured neighbour at the last greedy step.

This is greedy colouring with two precoloured neighbours.

Choose a spanning tree of the connected graph and root it at $x$. List vertices in nonincreasing order of their distance from $x$ in this tree, breaking ties arbitrarily. The root has distance zero and is last, so $v_n=x$.

Every other vertex has a parent one step closer to the root. That parent is adjacent to it and appears later in the ordering. HenceFor a graph of one vertex the condition is vacuous and the same ordering works.

Hall's marriage theorem says that a bipartite graph with parts $L,R$ has a matching saturating $L$ if and only ifNecessity follows because the matched neighbours of vertices of $S$ are distinct and belong to $N(S)$.

For sufficiency, assume these inequalities. Let $K=U\cup W$ be any vertex cover, with $U\subseteq L$ and $W\subseteq R$. Every neighbour of $S=L\setminus U$ must belong to $W$, since otherwise its edge from $S$ is uncovered. Therefore $|W|\ge |N(S)|\ge |S|$, and $|K|\ge |U|+|S|=|L|$. The whole part $L$ is itself a vertex cover of size $|L|$. Part (ii) now gives a matching of size exactly $|L|$, so it saturates $L$.

Let the bipartition be $L\cup R$. Form an auxiliary graph by adding a new vertex $s$ adjacent to every vertex of $L$ and a new vertex $t$ adjacent to every vertex of $R$. The vertices $s,t$ are nonadjacent, so Menger's theorem applies.

A matching of size $m$ gives $m$ internally disjoint graph paths $s\ell rt$, one for each matching edge $\ell r$. Conversely, every $s$-$t$ graph path must use an edge of the original bipartite graph. Choose one such edge from each member of an internally disjoint family. Their endpoints are all distinct, so the chosen edges form a matching. Thus the maximum number of those graph paths is the maximum matching size.

An $s$-$t$ separator contained in $L\cup R$ is exactly a vertex cover of the original graph. Indeed, an uncovered edge $\ell r$ would leave the graph path $s\ell rt$, while removing a vertex cover removes every edge between $L$ and $R$ and hence every $s$-$t$ graph path. The minimum separator size is therefore the minimum vertex cover size. Menger givesThis is Kőnig's theorem for bipartite matching. The auxiliary construction gives the required deduction from vertex-disjoint paths rather than assuming a matching theorem in advance.

The vertex version of Menger's theorem states that for two distinct nonadjacent vertices $s,t$ of a finite graph, the maximum number of internally vertex-disjoint $s$-$t$ graph paths equals the minimum size of a set $S\subseteq V\setminus \{s,t\}$ whose deletion separates $s$ from $t$.Internally disjoint graph paths may share their endpoints but no other vertex. The nonadjacency hypothesis is needed in this separator formulation, since an edge $st$ cannot be destroyed by deleting other vertices.

First take $0<p<1$ and $kp>1$. Part (a) gives an extinction probability $\eta \in (0,1)$. Write $p_j=\mathbb{P}(Z=j)$. Conditional on the ancestor having $j$ children, extinction requires extinction of all $j$ independent descendant trees and has probability ${\eta }^j$. Bayes' rule therefore gives the conditional offspring lawIts sum is $f(\eta )/\eta =1$. Conditional on extinction of all descendant trees, those trees remain independent, each with its own extinction-conditioned law. Thus the entire conditioned process is a Galton–Watson process with offspring generating functionFor binomial offspring, using $\eta =(1-p+p\eta {)}^k$ givesIts mean is $k\tilde{p}=f^{\prime }(\eta )<1$. Indeed, $f(s)-s$ is strictly convex and has its two zeros at $\eta$ and one, so its derivative at the first zero is strictly negative. This proves subcriticality directly from the generating function.

Let $T$ be total progeny, taking value infinity on survival. Apply part (b) to the conditioned process. For some $c>0$,Thus the unconditional tail tends to the positive survival probability $1-\eta$, with an exponentially small finite-extinction contribution. It does not decay to zero.

If $p=1$ and $kp>1$, extinction has probability zero and conditioning on it does not specify a probability law. In that deterministic case total progeny is infinite and $\mathbb{P}(T>n)=1$ for every finite $n$.

The nondegenerate law above is the binomial branching process conditioned on extinction.

Explore the family tree one individual at a time, maintaining a queue of individuals not yet explored. Initially its size is $Y_0=1$. Exploring individual $t$ removes it and adds its independent offspring $Z_t$, so before the queue empties,One may define the independent increments indefinitely, but the tree exploration stops at $T=\inf \{t:Y_t=0\}$. This hitting time is the total progeny, including the ancestor. Since each increment is at least $-1$, a queue cannot jump below zero before hitting zero. If it never hits zero, the family has infinitely many individuals.

Suppose $kp<1$. A Chernoff bound in moment-generating-function form says that for independent $W_j$ and $\theta >0$,Here take $W_j=Z_j-1$, withWe have $M(0)=1$ and $M^{\prime }(0)=kp-1<0$, so some $\theta >0$ has $M(\theta )<1$. Let $c=-\log M(\theta )>0$. If $T>n$, the queue is still positive after $n$ explorations; its integer value is at least one, giving ${\sum }_{j=1}^n(Z_j-1)\ge 0$. ThereforeThis proves the claimed bound without appealing to a general branching-process tail theorem.

The argument proves the more general exponential total progeny tail for bounded subcritical offspring.

A Galton-Watson process starts with one ancestor, $X_0=1$. Given generation size $X_r$, definewhere all offspring variables are independent with common distribution $Z$. The empty sum is zero, so zero is absorbing. Its extinction probability isFor the probability generating function $f(s)=\mathbb{E}[s^Z]$, the allowed fixed-point characterization isFor binomial offspring, $f(s)=(1-p+ps{)}^k$, with $f(1)=1$, $f^{\prime }(1)=kp$, and $f$ convex on $[0,1]$.

First assume $0<p<1$. If $k=0$, extinction occurs immediately. For $k=1$, $f(s)-s=(1-p)(1-s)>0$ for $s<1$, so the only fixed point is one. For $k\ge 2$, strict convexity givesIf $kp\le 1$, the right-hand side is at least $s$, so no fixed point below one exists and $\eta =1$. If $kp>1$, $f(s)-s<0$ for $s$ just below one, whereas $f(0)>0$. Continuity supplies a fixed point in $(0,1)$; hence $\eta <1$. Thus in the nondegenerate parameter range,For completeness, if binomial endpoint parameters are allowed, $p=0$ or $k=0$ gives $\eta =1$, while $p=1$ and $k\ge 1$ gives deterministic positive offspring and $\eta =0$. In particular $(k,p)=(1,1)$ survives forever despite mean one. Over $k\in \{0,1,\dots \}$ and $p\in [0,1]$, the full condition is

If there are no triangles, any edge colouring works. Otherwise $\Delta \ge 2$. Put $q=\lceil 3\sqrt{\Delta }\rceil$ and colour each edge independently and uniformly from $q$ colours. For each triangle $T$, let $A_T$ be the event that its three edges have one colour. ThenEvents for triangles sharing no edge depend on disjoint edge-colour variables, so each event is jointly independent of the collection of all such nonneighbours. Each edge of a triangle lies in at most $\Delta -2$ other triangles: a common neighbour of its endpoints must be one of at most $\Delta -1$ neighbours besides the other endpoint, and one of these is the third vertex of $T$ itself. Thus the dependency degree is at most $d=3(\Delta -2)$.

Because $q^2\ge 9\Delta$,The symmetric local lemma gives positive probability of avoiding every monochromatic triangle. HenceFor an edgeless graph the empty colouring handles even the zero-colour case $\Delta =0$.

The symmetric Lovász local lemma states: if each bad event has probability at most $p$, each event is independent of the collection of all but at most $d$ other events, andthen the probability that none of the bad events occurs is positive. Independence is from the sigma-algebra generated by the indicated nonneighbours, as in part (a). A sufficient sharper parameter condition is $p\le x(1-x{)}^d$ for some $x\in (0,1)$; taking $x=1/(d+1)$ gives the displayed standard bound when $d\ge 1$. When $d=0$, mutual independence directly gives the conclusion under the displayed bound.

A dependency digraph has vertices $1,\dots ,n$ and no loops. For each $i$, the event $A_i$ must be independent of the sigma-algebra generated jointly by all $A_j$ with $j\ne i$ for which there is no edge $i\to j$. Joint independence from that collection is required; pairwise independence alone does not suffice.

Write ${\Gamma }^{+}(i)$ for the outneighbours of $i$, and $B_S={\bigcap }_{j\in S}{A}_j^c$. We prove by induction on $|S|$ that $B_S$ has positive probability and, when $i\notin S$,For $S=\varnothing$, the asserted conditional bound follows from the hypothesis, since its product factors are at most one. For the induction step, positivity for a set of size $r$ follows by writing its avoidance probability as a chain product: all preceding conditioning sets have size below $r$, so each factor is at least $1-x_j>0$.

Now take $|S|=r$, split $S_1=S\cap {\Gamma }^{+}(i)$ and $S_2=S\setminus {\Gamma }^{+}(i)$, and condition first on $B_{S_2}$. Independence gives $\mathbb{P}(A_i\mid B_{S_2})=\mathbb{P}(A_i)$. Moreover, order the elements of $S_1$ and use the inductive conditional bounds on the successive avoidance factors. Their conditioning sets have size at most $r-1$, soThis remains true when $S_1$ is empty, with both sides one. ThereforeThe induction is complete. Finally expand the probability of avoiding all events in the order $1,\dots ,n$:This proves the asymmetric Lovász local lemma, including the positivity needed to make every conditioning step legitimate.