Year 3 of the mathematics course of the University of Oxford (Part B)

Eight units; extended essays or structured projects may replace some written units. Optional branches are a verified selection.

Original solutions to past examinations of the graph theory course of the University of Oxford.

Solutions to all three questions of the graph theory course of the University of Oxford Part B examination, sat on 15 June 2023. Source: original released PDF, bundle pages 243–244; paper pages 1–2. Throughout, graphs are finite simple graphs unless a construction explicitly permits parallel edges.

A proper edge colouring assigns colours to the edges of a graph so that distinct edges sharing a vertex have different colours. The edge chromatic number ${\chi }^{\prime }(G)$ is the least number of colours in such an assignment. Equivalently, it is the least number of matchings in a graph whose disjoint union is the entire collection of edges.

Vizing's theorem states that a finite simple graph of maximum degree $\Delta$ satisfiesThe lower bound holds because all edges incident with a vertex of vertex degree $\Delta$ require different colours.

Hall's marriage theorem states that a finite bipartite graph with vertex sets $A,B$ has a matching in a graph saturating $A$ if and only ifwhere $N(S)\subseteq B$ is the graph neighbourhood of $S$. Here matching saturation means that each vertex of $A$ is incident with an edge of the matching in a graph; it does not require every vertex of $B$ to be met.

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.

By part (i), choose a matching in a graph $M_1$ meeting all vertices of vertex degree $\Delta$ in $A$. Interchanging the two vertex sets gives a matching in a graph $M_2$ meeting all such vertices in $B$. Consider the spanning subgraph $H$ with edges $M_1\cup M_2$.

Every vertex has vertex degree at most two in $H$. An edge belonging to both matchings in a graph forms a whole two-vertex connected component of a graph, since neither endpoint can meet another edge of either matching in a graph. On every other nontrivial connected component of a graph, the edges alternate between $M_1$ and $M_2$, so the connected component of a graph is a graph path or an even graph cycle. We select one of the two matchings in a graph separately on each connected component of a graph.

On a graph cycle, either choice covers every vertex. On a graph path with an odd number of edges, the first and last edges belong to the same matching in a graph; choose it, and it covers every vertex of the graph path. For a common edge, choose that edge.

It remains to treat a graph path with a positive even number of edges. Its endpoints lie in the same side of the bipartite graph. Every internal vertex meets both matchings in a graph. If both endpoints lie in $A$, choose $M_1$: every endpoint of vertex degree $\Delta$ must already be met by $M_1$, by its defining property. If both endpoints lie in $B$, choose $M_2$ for the same reason. Thus the choice meets all vertices of vertex degree $\Delta$ in that connected component of a graph.

Finally, an isolated vertex of $H$ cannot have vertex degree $\Delta$ in $G$, since it would have been met by $M_1$ or $M_2$. The union of the selected edges over the connected components of a graph is a matching in a graph, because different connected components of a graph have disjoint vertex sets. It meets every vertex of vertex degree $\Delta$ in $G$. The useful mechanism is the union of two matchings and its alternating connected components of a graph.

Use mathematical induction on the maximum degree $\Delta$, including $\Delta =0$ as the base case. A graph of maximum degree zero has no edges, so zero colours suffice.

For $\Delta >0$, part (ii) supplies a matching in a graph $M$ meeting every vertex of vertex degree $\Delta$. Delete its edges, retaining all vertices. Each vertex formerly of maximum degree loses one incident edge; every other vertex already had vertex degree at most $\Delta -1$. HenceThe resulting graph is still a bipartite graph. By mathematical induction, it has a proper edge colouring using at most $\Delta -1$ colours. Give every edge of $M$ one new colour. Since $M$ is a matching in a graph, this produces a proper edge colouring of $G$ with at most $\Delta$ colours. The edges at a vertex of maximum degree require at least $\Delta$ colours, soThis is Kőnig's line colouring theorem.

For even $r\ge 2$, take the complete graph $K_{r+1}$. It is an $r$-regular graph on an odd number of vertices. Every matching in a graph has at most $r/2$ edges, so $r$ colours in a proper edge colouring could cover at most $r^2/2$ edges. ButTherefore ${\chi }^{\prime }(K_{r+1})>r$; Vizing's theorem gives ${\chi }^{\prime }(K_{r+1})=r+1$. This includes the graph triangle when $r=2$.

For odd $r\ge 3$, first construct a graph $H_r$ on $r+2$ vertices. Start with the complete graph onand delete the edges $va$, $vb$, and $c_1{c}_2,c_3{c}_4,\dots ,c_{r-2}{c}_{r-1}$. The pairing is possible because $r-1$ is even. In the initial complete graph, every vertex has vertex degree $r+1$. The distinguished vertex $v$ loses two edges and every other vertex loses exactly one, givingTake two disjoint copies of $H_r$, with distinguished vertices $v,v^{\prime }$, and add the edge $v{v}^{\prime }$. The resulting simple graph $G_r$ is an $r$-regular graph. The added edge is the only edge between the two copies; each copy has the odd number $r+2$ of vertices.

Suppose an $r$-colour proper edge colouring existed. At each vertex, the $r$ incident edges would use all $r$ colours. Thus each colour would form a perfect matching. Any perfect matching must use $v{v}^{\prime }$: without it, each odd-sized copy would have to be covered by internal pairs, which is impossible by parity. Therefore all $r$ colour classes would have to contain the same edge $v{v}^{\prime }$, a contradiction. Hence Vizing's theorem again givesThese constructions give class two regular graphs for every $r\ge 2$. The odd-$r$ construction exhibits the bridge obstruction to regular edge colouring; $H_r$ is a connected graph because every vertex other than $a,b,v$ is adjacent to $v$, while $a,b$ are adjacent to those vertices.

For a finite graph $G$, its chromatic polynomial $p_G(x)$ is the polynomial whose value at each positive integer $q$ counts proper vertex colourings of $G$ from a fixed palette of $q$ labelled colours. Adjacent vertices must receive different colours, and unused colours are allowed.

For an edge $e=uv$, the deletion-contraction recurrence for the chromatic polynomial isHere $G-e$ deletes only the edge $e$, while $G/e$ performs edge contraction, identifying $u,v$ and removing $e$. Any parallel edges produced by edge contraction can be replaced by a single edge, since their constraints on proper vertex colourings are identical.

Indeed, the proper vertex colourings of $G-e$ in which $u,v$ differ are precisely those of $G$, while those in which $u,v$ agree correspond bijectively to proper vertex colourings of $G/e$. This proves the equality for every positive integer $q$, hence as a polynomial identity. Together with $p_G(x)=x^{|V(G)|}$ for a graph without edges, the recurrence also proves by mathematical induction that the counting function is a polynomial.

Let the nonempty connected components of a graph of $G$ be $G_1,\dots ,G_t$. A proper vertex colouring can be chosen separately on each connected component of a graph, since no edge joins different connected components of a graph. The multiplication principle gives, first at positive integers and then as a polynomial identity,It remains to justify that every factor has zero constant term. More generally, for every nonempty simple graph $H$, prove $p_H(0)=0$ by mathematical induction on the number of edges. If there are no edges, then $p_H(x)=x^{|V(H)|}$ with $|V(H)|\ge 1$. Otherwise choose an edge $e$. Both $H-e$ and the simplified edge contraction $H/e$ are nonempty graphs with fewer edges. The deletion-contraction recurrence for the chromatic polynomial and mathematical induction giveThus $p_{G_j}(x)=x{q}_j(x)$ for a polynomial $q_j$, andFor the empty graph, $t=0$ and $p_G(x)=1$, so the conclusion also holds. This is the chromatic polynomial product over components.

Write $V=V(G)$ and $E=E(G)$. For $F\subseteq E$, let $c(F)$ denote the number of connected components of a graph of the spanning subgraph $(V,F)$, including isolated vertices. The inclusion-exclusion principle, applied to the unwanted events that the two endpoints of an edge receive the same colour, gives the chromatic polynomial inclusion-exclusion formulaTo justify the exponent, imposing equal colours across all edges in $F$ forces a single colour on each connected component of a graph of $(V,F)$, with independent choices between its connected components of a graph. Thus the corresponding count at $q$ colours is $q^{c(F)}$. Equality for all positive integers proves the polynomial identity.

Fix an index $i$ in the stated range. A subset $F$ contributes to the coefficient of $x^{n-i}$ exactly when $n-c(F)=i$. If $(V,F)$ contains a graph cycle of length $s$, the hypothesis gives $s\ge \ell$. All its $s$ vertices lie in one connected component of a graph. For any connected component of a graph $D$, its contribution to $n-c(F)$ is $|V(D)|-1$, soThis contradicts $i\le \ell -2$. Therefore every contributing $(V,F)$ is a forest. The forest identity $|F|=n-c(F)$ then gives $|F|=i$.

Conversely, every $i$-edge subset is a forest, since a graph cycle in it would have at most $i<\ell$ edges. It therefore has $c(F)=n-i$ and contributes exactly $(-1{)}^i$. There are $\left(\genfrac{}{}{0ex}{}{m}{i}\right)$ such subsets, by the definition of a binomial coefficient. ConsequentlyHere the coefficient notation is understood within the defined indices $0\le i\le n$; if the displayed range is extended past $n$, the coefficients beyond the constant term can be set to zero. For a forest, $m\le n-1$, so the binomial coefficients there are also zero. The key reason girth determines initial chromatic coefficients is that a graph cycle can affect only exponents whose loss of connected components of a graph is at least $\ell -1$.

First reduce the unicyclic graph to its unique graph cycle $C$. Delete the edges of $C$ but retain every vertex. The remaining graph is a forest, since any surviving graph cycle would be a second one in $G$. Each of its connected components of a graph contains a vertex of $C$: follow a graph path to $C$ in the original connected graph, stopping at the first vertex of $C$; this initial segment uses no edge of $C$.

No such connected component of a graph contains two vertices of $C$. Otherwise, on the tree graph path between them, choose two successive visits to $C$. The segment between these visits has no internal vertex on $C$ and uses no edge of $C$. Combining it with either connecting arc of $C$ gives a second graph cycle, a contradiction. Thus the remaining graph consists of trees, each rooted at exactly one vertex of $C$.

After choosing a proper vertex colouring of $C$ from $q$ colours, colour these rooted trees away from their roots. Each of the $n-\ell$ off-graph cycle vertices has one already coloured parent in a rooted tree, leaving exactly $q-1$ choices. The multiplication principle therefore givesEquivalently, this repeatedly applies the chromatic polynomial after attaching a leaf formula.

To compute the chromatic polynomial of a cycle, the base case is the graph triangle:For $s\ge 4$, deleting a cycle graph edge gives a path graph on $s$ vertices, while edge contraction gives $C_{s-1}$. The chromatic polynomial of that path graph is $x(x-1{)}^{s-1}$, by choosing the colour of its first vertex and then each successive vertex. Hence the deletion-contraction recurrence for the chromatic polynomial givesUsing mathematical induction, substitute $p_{C_{s-1}}(x)=(x-1{)}^{s-1}+(-1{)}^{s-1}(x-1)$ to obtainMultiplying by the factor for the attached trees proves the chromatic polynomial of a unicyclic graph formula

A graph is a k-connected graph if it has at least $k+1$ vertices and deleting any set of fewer than $k$ vertices, together with their incident edges, leaves a connected graph.

The vertex connectivity $\kappa (G)$ is the largest such $k$. Equivalently, for a graph with at least two vertices, it is the smallest number of vertices whose deletion either disconnects the graph or leaves a single vertex. The latter convention gives $\kappa (K_n)=n-1$ for a complete graph. A disconnected graph has vertex connectivity zero; one usually also sets $\kappa (K_1)=0$.

For distinct nonadjacent vertices $x,y$, the local connectivity isSuch a set $S$ is an $x$–$y$ vertex separator. By Menger's theorem, local connectivity also equals the maximum number of internally vertex-disjoint paths from $x$ to $y$. If no graph path exists already, the empty vertex separator gives zero.

The vertex separator version of Menger's theorem says that, for distinct nonadjacent vertices $x,y$ of a finite graph, the maximum number of internally vertex-disjoint paths from $x$ to $y$ equals the minimum size of an $x$–$y$ vertex separator.

Use the following version of the max-flow min-cut theorem: in a finite directed flow network with nonnegative integer flow network edge capacities, the maximum flow value equals the minimum cut capacity, and a maximum flow can be chosen to have integer values on every directed edge. The last clause is the integral max-flow theorem.

Here is the reduction, including the correspondence with vertex separators. Put $N=|V(G)|$. Perform vertex splitting on each vertex $v\ne x,y$, replacing it by $v_{\mathrm{in}},v_{\mathrm{out}}$ with a directed edge $v_{\mathrm{in}}\to v_{\mathrm{out}}$ of flow network edge capacity one. Keep $x$ as the source and $y$ as the sink. For each original undirected edge $uv$, put directed edges from the output of $u$ to the input of $v$ and from the output of $v$ to the input of $u$, each of flow network edge capacity $N$; an unsplit endpoint uses $x$ or $y$ itself.

A family of $p$ internally vertex-disjoint paths gives a feasible integral flow of value $p$, by sending one unit down each graph path. Conversely, decompose an integral flow into unit source-to-sink graph paths and directed cycles, discarding the directed cycles. This decomposition can be obtained by following positive-flow directed edges and subtracting one unit along a source-to-sink graph path or a directed cycle, repeating until the flow value is exhausted. A capacity-one split edge can belong to at most one unit graph path. The projected graph paths in $G$ are therefore internally vertex-disjoint paths. Thus the largest number of such graph paths equals the maximum flow value.

Deleting a vertex separator $S$ corresponds to removing its split edges, of total flow network edge capacity $|S|$. This destroys every source-to-sink graph path; taking the source-reachable vertices after removal gives a cut of a flow network of cut capacity at most $|S|$. Thus the minimum cut capacity is no greater than the minimum vertex separator size.

For the reverse inequality, deleting all $N-2$ internal vertices separates $x,y$, because they are nonadjacent. Hence a minimum cut has cut capacity at most $N-2<N$ and cannot contain a directed edge of flow network edge capacity $N$. Its outgoing edges are therefore split edges. Let $S$ be the original vertices associated with them. Any $x$–$y$ graph path avoiding $S$ would lift to a source-to-sink graph path crossing this cut of a flow network without using an outgoing edge, an impossibility. Hence $S$ is a vertex separator, with size exactly the cut capacity. The two minima agree, and the max-flow min-cut theorem proves Menger's theorem.

Add two new vertices $s,t$ to $G$, joining $s$ to every vertex of $U$ and $t$ to every vertex of $W$, with no other new edges. The vertices $s,t$ are nonadjacent. Suppose $S\subseteq V(G)$ has $|S|<k$. Since $G$ is a k-connected graph, $G-S$ is a connected graph. Both $U\setminus S$ and $W\setminus S$ are nonempty because each original set has cardinality $k$. Choose $u\in U\setminus S$ and $w\in W\setminus S$; a graph path between them in $G-S$ extends to an $s$–$t$ graph path avoiding $S$.

Consequently no fewer than $k$ vertices can form an $s$–$t$ vertex separator. By Menger's theorem, there are at least $k$ internally vertex-disjoint paths from $s$ to $t$. There cannot be more than $k$, since $s$ has only $k$ neighbours.

Remove $s,t$ from these $k$ graph paths. The resulting graph paths in $G$ start at distinct vertices of $U$, end at distinct vertices of $W$, and are pairwise vertex-disjoint paths: any shared vertex would have been an internal vertex common to two of the original graph paths. Because there are exactly $k$ graph paths, they use every vertex of $U$ and $W$ as an endpoint. None can pass through another terminal internally, since that terminal already occurs as an endpoint of one of the vertex-disjoint paths. Thus there are $k$ vertex-disjoint paths from $U$ to $W$, with some pairing of the endpoints. This is also an immediate application of the Set version of Menger theorem.

No. A counterexample works for every $k\ge 2$. Take the complete bipartite graph $G=K_{k,k}$ with vertex setsIt is a k-connected graph: deleting fewer than $k$ vertices leaves at least one vertex in each side, and the remaining complete bipartite graph is a connected graph.

Chooseand order these sets so that $u_1=b_1$ and $w_1=b_2$. Order the other members arbitrarily. These are disjoint sets of cardinality $k$, and every vertex of $G$ is one of the specified endpoints.

If the prescribed $k$ vertex-disjoint paths existed, no one of them could have an internal vertex, because every vertex must serve as the endpoint of one of the graph paths. Thus each graph path would have to be a single edge. But $b_1,b_2$ lie in the same side of the bipartite graph, so there is no edge $b_1{b}_2$. This contradicts the requirement on $P_1$.

For $k=2$ this is the four-vertex cycle graph, with opposite vertices paired. The stronger property that every prescribed pairing can be realized is the linked graph property; vertex connectivity alone does not guarantee it.

We verify the Hall condition for $U$. Let $S\subseteq U$. If $S$ is empty, then $|N(S)|=0=|S|$. Suppose $0<|S|\le n/2$. Choose $u\in S$. Its graph neighbourhood is contained in $N(S)$, so the minimum degree hypothesis givesIf $|S|>n/2$, suppose for a contradiction that some vertex $w\in W\setminus N(S)$ exists. All neighbours of $w$ lie in $U\setminus S$, socontradicting the minimum degree hypothesis. Thus $N(S)=W$ and $|N(S)|=n\ge |S|$.

Every subset $S\subseteq U$ satisfies the Hall condition. By Hall's marriage theorem, there is a matching in a graph saturating $U$. Since $|U|=|W|=n$, its $n$ edges also cover every vertex of $W$. It is therefore a complete matching, meaning a perfect matching. For $n=0$, the empty matching in a graph already has this property.

The shared 2022 paper is skipped here because the Mathematical Institute advertises student answers for papers in even years. The individual answer file has not been inspected.^[ref]

Student answer archive (Oxford sign-on required): courses.maths.ox.ac.uk/course/view.php?id=6499

Source paper: www.whatdotheyknow.com/request/ba_computer_science_past_papers/response/2577745/attach/2/202402%20183%20CS%20Papers.zip?cookie_passthrough=1

Solutions to all three questions.^[ref] All logarithms are base two; information entropy is measured in bits and code rates in bits per channel use. Terms $0\log 0$ are zero. Question 3(b) contains an incorrect hint; its requested conclusion is proved directly below for deterministic channel codes. The repeat-until-success protocol in Question 3(c) requires $q<1$ to terminate.

The inequality is true for ordinary addition, and also for addition in a group. For any fixed $y$, the translation $x\mapsto x+y$ is injective, so it merely relabels the probability masses in the conditional distribution. Since $X,Y$ are independent random variables,Averaging over $y$ and using conditioning reduces entropy proves entropy monotonicity under independent addition:There is no requirement that $X+Y$ remain in the original finite alphabet. The proof also gives $H(X+Y)\ge H(Y)$ by symmetry. Independence matters: for a nonconstant $X$ and $Y=-X$, the sum is constant while $H(X)>0$.

Let $N=|\mathcal{X}|\ge 2$ and let $E=1_{\{X\ne Y\}}$ be the error indicator random variable. Because $E$ is determined by $(X,Y)$, the chain rule for conditional entropy in its two orders givesBy conditioning reduces entropy, $H(E\mid Y)\le H(E)$. On $E=0$, knowing $Y$ determines $X$, so the corresponding conditional entropy is zero. On $E=1$, at most $N-1$ symbols remain possible for $X$. The maximum Shannon entropy of a probability distribution on at most $N-1$ symbols is $\log (N-1)$. ConsequentlyFor an arbitrary function $g:\mathcal{X}\to \mathcal{X}$, repeat the argument with $E_g=1_{\{X\ne g(Y)\}}$. This is still determined by $(X,Y)$; when it is zero, $X=g(Y)$, and when it is one, $X$ has at most $N-1$ possibilities for each $Y$. Thus Fano's inequality givesEvents of zero probability contribute zero to the conditional average, covering the error probabilities zero and one. If $N=1$, the left side and error probabilities are zero; the trivial conclusion is handled separately instead of writing $0\log 0$ as an ordinary finite product.

For the entropy summand $f(x)=-x\log x$, differentiation on $(0,1)$ givesSince $f(x)\to 0$ as $x\downarrow 0$, its continuous extension to $[0,1]$ is a concave function.

Fix $0<v<1$ and define the increment $D_v(t)=f(t+v)-f(t)$ on $[0,1-v]$. In its interior,Thus the increment is decreasing, and its endpoint values are $D_v(0)=f(v)$ and $D_v(1-v)=-f(1-v)$. ThereforeThe cases $v=0,1$ follow directly from the endpoint values.

To obtain the sharper half-interval bound, put $G(v)=f(v)-f(1-v)$. It has $G(0)=G(1/2)=0$, whileHence $G$ is a concave function on $[0,1/2]$ and lies above the chord joining its zero endpoints. Thus $f(v)\ge f(1-v)$ there, proving

Set $N=|\mathcal{X}|$, $d_i=|p_i-q_i|$ and $d={\sum }_i{d}_i=\Vert p-q{\Vert }_1$. If $d=0$, the two probability mass functions agree and the bound is zero. Otherwise every $d_i\le d\le 1/2$. The half-interval entropy summand bound, with $t=\min (p_i,q_i)$ and $v=d_i$, givesBy the triangle inequality, followed by Jensen's inequality for the concave function $f$,This proves the requested finite-alphabet entropy continuity bound:

The independent and identically distributed hypothesis factors the joint probability mass function:Symbols outside the support of a probability distribution $p$ never occur, almost surely. On its finite positive probability support, $\log p(X_i)$ is bounded, so the strong law of large numbers applies:This is the asymptotic equipartition property with the sign appropriate to a logarithm of a probability mass.

For a fixed estimated probability mass function $q$, the estimated joint probability mass function is $q_n(x_1,\dots ,x_n)={\prod }_{i}q(x_i)$. If $q(x)>0$ whenever $p(x)>0$, the strong law of large numbers gives the mismatched asymptotic equipartition property:Here $H(p,q)$ is cross-entropy, and the last equality is cross-entropy equals entropy plus relative entropy. The Kullback-Leibler divergence measures the extra average logarithmic loss from the estimated law.

If $q(x)=0$ for some $x$ with $p(x)>0$, let $a={\sum }_{x:q(x)=0}p(x)>0$. The probability that none of the first $n$ observations belongs to this set is $(1-a{)}^n\to 0$. Almost surely such a symbol eventually occurs, after which $q_n(X_1,\dots ,X_n)=0$ forever. Thus the limit is $-\infty$, consistent with infinite cross-entropy and infinite Kullback-Leibler divergence.

For every $x^n\in A^{n,\epsilon }$, the defining typical set constraint impliesLet $S_n=A^{n,\epsilon }\cap B^{n,\epsilon }$. Summing the lower probability mass bound over $S_n$ givesThereforeThe sample mean constraint can only shrink the typical set, so this cardinality upper bound holds for every positive integer $n$.

For fixed $\epsilon >0$, the asymptotic equipartition property gives $\mathrm{Pr}(X^n\notin A^{n,\epsilon })\to 0$. The strong law of large numbers applied to $X_i$, which are bounded because their numerical alphabet is finite, gives $\mathrm{Pr}(X^n\notin B^{n,\epsilon })\to 0$. The union bound therefore yieldsSince $\delta >0$, eventually $\mathrm{Pr}(X^n\in S_n)\ge 2^{-\delta }$. Each word in $S_n$ has probability mass at most $2^{-n(H(p)-\epsilon )}$, soRearranging provesfor sufficiently large $n$. The key is that the factor $2^{-\delta }$ is a fixed number below one, however small $\delta$ is. This is an instance of typical sets with an additional high-probability constraint.

First, the binary translation of a quaternary prefix code is still a prefix code: every translated codeword length is even, and a binary prefix relation would split into complete two-bit blocks, giving a prefix relation between the original quaternary codewords. Binary Huffman coding is optimal among binary prefix codes, soFor the other direction, let ${\ell }_i=|c_B(x_i)|$ and round these binary codeword lengths to quaternary lengths $k_i=\lceil {\ell }_i/2\rceil$. The Kraft inequality givesThe quaternary converse of the Kraft inequality supplies a quaternary prefix code with lengths $k_i$. Optimality of the quaternary Huffman code then impliesThus binary translation of an optimal quaternary code costs at most one extra bit per source symbol:The quaternary Huffman code uses the usual adjustment of adding zero-weight dummy leaves when needed. If the alphabet has one symbol, both optimal codes may use the empty codeword, giving the trivial endpoint.

The specified transition law is a binary erasure channel. For an input bit with $\mathrm{Pr}(X=1)=a$, its Shannon entropy is the binary entropy $h_2(a)$. A non-erased output determines $X$, whereas the erasure symbol leaves its probability distribution unchanged because the erasure event is independent of $X$. ThusMaximizing the mutual information over the input probability distribution, $h_2(a)\le 1$ with equality at $a=1/2$, givesThis includes $q=0$, a noiseless binary channel, and $q=1$, a completely erased channel with zero channel capacity.

Use the standard deterministic channel encoder and channel decoder, with $m$ message labels and code rate $R=(\log m)/n$. The Fano's inequality hint printed here replaces $\log (m-1)$ by $\log m-1$, which is false in general: take $X$ uniform on $\{0,1\}$ and $Y=2$ in the common alphabet $\{0,1,2\}$. The error probability is one and its binary entropy is zero, so the proposed bound asserts $1\le \log 3-1<1$. The correct Fano's inequality alone gives $(1-P_e)\log m\le n(1-q)+h_2(P_e)$, which does not immediately give the requested additive $1/n$. The following erasure-pattern counting bound for maximal decoding error proves the displayed claim directly.

The case $m\le 2$ is immediate because $R\le 1/n$. Suppose $m>2$, put $L=\log m-1>0$, and let $w_0$ be the message that the channel decoder returns on the all-erased output. Choose $W$ uniformly among the other $m-1$ messages. Every one of these messages is decoded correctly with probability at least $1-\delta$, by the assumed maximal decoding error probability bound.

Let $S$ be the random set of unerased coordinates and $K=|S|$. For each fixed $S$ with $K=k\ge 1$, at most $2^k$ output words are possible. A deterministic channel decoder can correctly identify at most one message per output word, so its conditional success probability, averaged over these $m-1$ messages, is at most $\min \{1,2^k/(m-1)\}$. When $K=0$, success is zero because $w_0$ was excluded.

For every integer $k\ge 1$,If $k\ge L$, this is immediate. If $k<L$, write $r=m/2^k>2$. The elementary inequality $\log r\le r-1$ for $r\ge 2$ giveswhere the middle inequality is $(k-1)(r-2)\ge 0$. This proves the needed scalar bound.

Taking the expectation over erasure patterns, and using $\mathbb{E}K=n(1-q)$, yieldsConsequently the requested bound is valid:The use of maximal decoding error probability matters: excluding one message preserves the lower bound on success. The deterministic channel decoder convention also matters; allowing independent randomized guessing would invalidate this particular finite-length claim at $q=1$.