Past exam of the mathematics course of the University of Cambridge / 2010 / ii / Paper 2

For an odd prime number $p$ and an integer $n$ not divisible by $p$, the Legendre symbol $\chi (n)=(n/p)$ is $1$ if $n$ is a quadratic residue modulo $p$, and $-1$ otherwise. One may extend it by $\chi (n)=0$ when $p\mid n$.

Put $h=(p-1)/2$. The nonzero quadratic residues in the finite field ${\mathbb{F}}_p$ form a subgroup of size $h$: the group homomorphism $x\mapsto x^2$ has kernel $\{1,-1\}$. Each square satisfies $u^h=1$ by Fermat's little theorem. Since a nonzero polynomial of degree $h$ has at most $h$ roots of a polynomial, these are all the roots of $X^h-1$. For any other nonzero $u$, Fermat's theorem gives $(u^h{)}^2=1$, so $u^h=-1$. Thus Euler's criterion follows, and multiplication givesBoth sides are $1$ or $-1$, which are distinct modulo the odd prime number $p$, so $\chi (mn)=\chi (m)\chi (n)$. Taking $n=-1$ in Euler's criterion gives $\chi (-1)=(-1{)}^{(p-1)/2}$, which is $1$ for $p\equiv 1(\mathrm{mod}4)$ and $-1$ for $p\equiv 3(\mathrm{mod}4)$.

Euler's criterion gives $\chi (-1)=(-1{)}^{(p-1)/2}=1$ in this case. There are equally many nonzero quadratic residues and quadratic nonresidues, so ${\sum }_{n=1}^{p-1}\chi (n)=0$. Replacing $n$ by $p-n$ and using the multiplicativity of the Legendre symbol givesConsequently $\boxed{S=0}$.

The Weierstrass approximation theorem says that for every real continuous function $f$ on $[0,1]$ and every $\epsilon >0$, there is a real polynomial $P$ with ${\sup }_{[0,1]}|f-P|<\epsilon$. Equivalently, polynomials are dense in $C[0,1]$ in the uniform norm.

The given moments imply ${\int }_0^{1}f(x)P(x)dx=0$ for every polynomial $P$. Choose polynomials $P_k$ converging uniformly to $f$ by the Weierstrass approximation theorem. ThenA nonnegative continuous function with zero integral vanishes everywhere. Hence $f=0$.

This also forces $f=0$. Indeed, $h(t)=f(\sqrt{t})$ is a continuous function on $[0,1]$. Approximate $h$ uniformly by polynomials $P_k(t)$ using the Weierstrass approximation theorem. Then $P_k(x^2)\to f(x)$ uniformly, and the even moments give $\int f(x)P_k(x^2)dx=0$. The estimate from part (i), with $P_k(x^2)$ in place of $P_k(x)$, proves $\int f^2=0$ and hence the conclusion.

Again $f=0$. The change of variables $t=x^2$ givesApply part (i) to the continuous function $h(t)=f(\sqrt{t})$. It vanishes on the whole interval, so does $f$.

Let $v=T(0)$ and $B(x)=T(x)-v$. The Euclidean isometry $B$ fixes the origin and preserves norms. The polarization identity therefore gives $⟨Bx,By⟩=⟨x,y⟩$. In particular, $B{e}_1,B{e}_2$ are an orthonormal basis. The coefficients of $Bx$ in this basis are $⟨Bx,B{e}_j⟩=x_j$, so $Bx=x_{1}B{e}_1+x_{2}B{e}_2$. Thus $B$ is a linear map represented by an orthogonal matrix, and $T(x)=Bx+v$. Conversely, every such map preserves distances because $\Vert B(x-y)\Vert =\Vert x-y\Vert$.

When $\det B=-1$, the real eigenvalues of the two-dimensional orthogonal matrix are $1,-1$. Choose corresponding unit eigenvectors $e,n$, and write $v=ae+bn$. In these coordinates $T(s,t)=(s+a,-t+b)$. This is reflection in the line $t=b/2$, followed by translation $ae$ along that line. It is a Euclidean reflection if $a=0$, and a glide reflection if $a\ne 0$.

Take the parity-check matrixover ${\mathbb{F}}_2$. Its columns are all the nonzero vectors of ${\mathbb{F}}_2^3$. The Hamming code is $C=\ker H$. Since $H$ has rank three, $C$ is a binary linear code of length seven and dimension four. No nonzero codeword has weight one or two, since no column is zero and no two columns coincide. Columns $u,v,u+v$ give a codeword of weight three, so $C$ has parameters $[7,4,3]$.

For a received vector $w=c+e$, its syndrome is $Hw=He$. A single error in position $j$ gives exactly column $j$ of $H$, so the syndrome identifies that position uniquely; zero syndrome means no error under the one-error assumption. The radius-one Hamming balls around the $16$ codewords are disjoint and have total size $16(1+7)=128=2^7$, so this is also a perfect code.

There are $\left(\genfrac{}{}{0ex}{}{7}{2}\right)/3=7$ weight-three codewords: every pair of columns determines the third, and each triple is counted three times. The all-ones vector is a codeword because the column sum is zero, so complementation gives seven weight-four codewords. Together with zero and the all-ones vector these account for all sixteen. The weight enumerator is therefore

A maximum-likelihood estimator maximizes the likelihood as a function of the parameter for the observed data. Under the usual regularity conditions, a scalar maximum-likelihood estimator satisfies $\sqrt{n}(\hat{\theta }-\theta )\Rightarrow N(0,I_1(\theta {)}^{-1})$, where $I_1$ is the Fisher information in one observation.

For a Poisson distribution with $\theta >0$, the log-likelihood is $\ell (\theta )={\sum }_j{Y}_j\log \theta -n\theta -{\sum }_j\log (Y_j!)$. Solving ${\ell }^{\prime }(\theta )=0$ gives $\boxed{\hat{\theta }=\bar{Y}}$. Its expectation is $\theta$ and its variance is $\theta /n$. If all observations are zero, the maximum over $\theta \ge 0$ occurs at zero; over $\theta >0$ this is a boundary supremum. The one-observation score function is $Y/\theta -1$, so $I_1(\theta )=\mathrm{Var}(Y)/{\theta }^2=1/\theta$ and the asymptotic variance of $\sqrt{n}(\bar{Y}-\theta )$ is $\theta$.

For $n\ge 2$, let $S=(n-1{)}^{-1}{\sum }_j(Y_j-\bar{Y}{)}^2$. The identitygives $\mathbb{E}S=(n\theta -\theta )/(n-1)=\theta$, so $S$ is another unbiased estimator. However, the total score function has variance $n/\theta$. For any regular unbiased estimator $T$, differentiating ${\mathbb{E}}_{\theta }T=\theta$ gives $\mathrm{Cov}(T,{\ell }^{\prime })=1$, so the Cauchy-Schwarz inequality yields $\mathrm{Var}(T)\ge \theta /n$. The sample mean attains this Cramér-Rao bound exactly. There is no variance advantage in preferring $S$ to $\bar{Y}$.

Write $f(u)=a{u}^2/(b^2+u^2)$, with $b>0$. Besides zero, the fixed points satisfy $u^2-au+b^2=0$. If $a^2>4b^2$, they areThe derivative is $f^{\prime }(u)=2a{b}^{2}u/(b^2+u^2{)}^2$. At a positive fixed point, $b^2+u^2=au$, so $f^{\prime }(u)=2b^2/(au)=2(1-u/a)$. Thus zero is attracting, $u_{-}$ is repelling because $f^{\prime }(u_{-})>1$, and $u_{+}$ is attracting because $0<f^{\prime }(u_{+})<1$.

Moreover,For $0<u_0<u_{-}$ the iterates strictly decrease and stay positive. Their limit is a fixed point below $u_{-}$, hence zero. For $u_{-}<u_0<u_{+}$ the iterates increase towards $u_{+}$; for $u_0>u_{+}$ they decrease towards $u_{+}$. Monotonicity of $f$ prevents crossing the limiting fixed point. $u_{-}$ is the extinction threshold. The cobweb plot illustrates these alternatives.

For $a^2<4b^2$ there are no positive fixed points, and $f(u)<u$ for every $u>0$, so all populations tend to zero. At $a^2=4b^2$, the positive fixed point $a/2$ is semistable: initial populations below it tend to zero, and those above it decrease towards it. This is a saddle-node bifurcation in the discrete dynamics.

The only equilibrium point is $(0,0)$. Its Jacobian matrix is $\left(\begin{array}{cc}-\mu & 1\\ -1& 0\end{array}\right)$, with characteristic polynomial ${\lambda }^2+\mu \lambda +1$. For $\mu >0$ both eigenvalues have negative real parts, so the origin is locally asymptotically stable.

Use the Lyapunov function $V=(x^2+y^2)/2$. Along a solution,A Lyapunov function is positive away from the equilibrium and nonincreasing along trajectories; its sufficiently small sublevel sets prove stability. Asymptotic stability additionally means nearby trajectories converge to the equilibrium. The basin of attraction is the set of initial states whose forward solutions exist for all positive time and converge to it. Every closed disc of radius at most $\sqrt{3}$ is positively invariant, since $\dot{V}\le 0$ there. The LaSalle invariance principle says that a solution in a compact positively invariant set where $\dot{V}\le 0$ approaches the largest invariant subset of $\{\dot{V}=0\}$. Here that subset is only the origin: on $x=0$, remaining on the line would require $y=0$; the isolated points $x=\pm \sqrt{3},y=0$ on the outer disc do not remain there because $\dot{y}=-x\ne 0$. Hence the closed disc $x^2+y^2\le 3$ lies in the basin of attraction.

This estimate does not assert that the basin is exactly that disc, or the whole plane. For example, choose $R$ so large that $R^2\ge 6(\mu +1)/\mu$ and $R^2>3(\mu +2)/\mu$. The region $x\ge R,y\ge -x$ is positively invariant: on $x=R$ one has $\dot{x}>0$, and on $y=-x$ one has $(x+y{)}^{\cdot }=\mu x^3/3-(\mu +2)x>0$. Within it $\dot{x}\ge \mu x^3/6$, which forces finite-time escape. Thus the attraction is genuinely local. The Lyapunov function gives a rigorous sufficient domain for attraction without identifying its entire boundary.

The removable singularities at zero are understood inThese are entire functions, with values $F^{+}(0)=1/2$ and $F^{-}(0)=-1/2$. On the real axis their difference is $\sin x/x$, including its continuous value at zero. In the complex upper half-plane, $|e^{iz}|\le 1$, so $|F^{+}(z)|\le 1/|z|$ away from zero; the analogous bound for $F^{-}$ holds in the lower half-plane. This verifies analyticity, the required jump and the specified decay.

In the Sokhotski–Plemelj formula, the boundary values may also be writtenIndeed the Cauchy principal value of $\sin t/[t(t-x)]$ is $\pi (\cos x-1)/x$: split $1/[t(t-x)]=x^{-1}((t-x{)}^{-1}-t^{-1})$, translate the first integral, and use ${\int }_{\mathbb{R}}\sin t/tdt=\pi$ and the oddness of $\cos t/t$. The limiting formula at zero follows continuously.

For $T=\frac{1}{2}{\dot{q}}^{T}T\dot{q}$ and $V=\frac{1}{2}{q}^{T}Vq$, where the matrices are symmetric and constant, the Euler-Lagrange equations give $T\ddot{q}+Vq=0$. A normal mode $q=v{e}^{i\omega t}$ therefore solves $(V-{\omega }^{2}T)v=0$.

A string segment of horizontal length $b$ has extension $\sqrt{b^2+(\Delta q{)}^2}-b=(\Delta q{)}^2/(2b)+O((\Delta q{)}^4)$. Multiplying by the tension $S$ and using $m=1$ and $S/b=1$, the quadratic kinetic energy and potential energy areThus $T=I$ and $V=\left(\begin{array}{ccc}2& -1& 0\\ -1& 2& -1\\ 0& -1& 2\end{array}\right)$. Taking $v_i=\sin (ij\pi /4)$, $i=1,2,3$, gives the three eigenvalues $2-2\cos (j\pi /4)$, $j=1,2,3$. The normal mode frequencies are

The photon number density is obtained by integrating the Planck photon distribution. With $x=h\nu /(kT)$,The integral converges, since its integrand is of order $x$ near zero and decays exponentially at infinity. Hence $n=\alpha T^3$, with $\alpha$ independent of temperature.

For equilibrium radiation undergoing adiabatic expansion, the total entropy in a comoving volume is constant. Since the entropy density is $\beta T^3$, this means $\beta T^{3}V$ is constant. A comoving volume scales as the cube of the scale factor, soThis agrees with the cosmological redshift of each photon frequency. The conclusion uses entropy conservation during the expansion.

The planar Brouwer fixed-point theorem states that every continuous map from a closed disc to itself has a fixed point.

Suppose first that a retraction $R:D\to C$ exists. The continuous map $p\mapsto -R(p)$ takes $D$ to itself, so the Brouwer fixed-point theorem gives $p=-R(p)$. Such $p$ lies on $C$, where $R(p)=p$, contradicting $p=-p$.

Conversely, suppose a continuous map $T:D\to D$ has no fixed point. For each $p$, follow the ray from $T(p)$ through $p$ to its last intersection with $C$. This defines a retraction. More explicitly, put $a=p-T(p)\ne 0$ and setThe positive-root formula is continuous, $t(p)\ge 1$, and $R(p)$ is on the unit circle. If $p\in C$, the last intersection is $p$ itself, so $R(p)=p$. Thus the nonexistence of a retraction rules out a fixed-point-free $T$, proving the equivalence.

Fix $z$ with $|z|<1-\epsilon$, and let $\Pi (w)=w/\max (1,|w|)$ be radial projection to the closed disc. The continuous map $p\mapsto \Pi (p-G(p)+z)$ has a fixed point $p$ by the Brouwer fixed-point theorem. On the boundary, $|p-G(p)+z|<\epsilon +|z|<1$, so its image under $\Pi$ is interior and cannot equal the boundary point $p$. Therefore $p\in B$. An interior fixed point of this projection must satisfy $p-G(p)+z=p$, because points outside the disc project to its boundary. Thus $G(p)=z$. Every $z\in B_{1-\epsilon }(0)$ belongs to $G(B)$.

No such map exists. If $H$ fixed the boundary, it would satisfy the hypothesis of part (iii) for every $\epsilon >0$. Choose $0<\epsilon <1-|q|$. Then part (iii) would give $q\in H(B)$, contradicting the stipulated omission of $q$. Equivalently, radial projection from the omitted point would turn $H$ into a forbidden retraction.

The Vandermonde determinant isIndeed, the determinant is an alternating polynomial, hence divisible by every $x_j-x_i$. Both sides have degree $r(r-1)/2$, and comparison of the coefficient of $x_0^0{x}_1^1\cdots x_{r-1}^{r-1}$ gives constant one. This is an identity over the integers, so reducing its coefficients modulo a prime number preserves it. For $r>p$, two residues coincide and the determinant vanishes. For $r=p$, choose all elements of ${\mathbb{F}}_p$ once to obtain a nonzero determinant.

For the ordering $0,1,\dots ,p-1$, this determinant is $D={\prod }_{j=1}^{p-1}j!$. If $p$ is odd, put $h=(p-1)/2$. Wilson theorem gives $j!(p-1-j)!=(-1{)}^{j+1}$. Pairing the factors with indices $j=0,\dots ,h-1$ and $p-1-j$, and leaving $h!$ unpaired, givesEvery distinct ordering changes the determinant by its permutation sign; repeated residues give zero. Thus the possible values are $0,\pm h!$ for odd $p$, and $0,1$ for $p=2$.

Use Shamir's secret sharing: choose independent uniform $a_1,\dots ,a_{r-1}\in {\mathbb{F}}_p$, and engrave the shares $(x_i,P(x_i))$, where $P(X)=N+{\sum }_{j=1}^{r-1}{a}_j{X}^j$ and the $x_i$ are distinct nonzero field elements. We may take $p>n$; otherwise use a sufficiently large finite field extension and an agreed integer encoding. Any $r$ shares determine $P$ by polynomial interpolation and hence $N=P(0)$. Given any $r-1$ shares and any proposed $N$, their equations in the coefficients have a unique solution: the coefficient matrix has determinant ${\prod }_i{x}_i$ times a nonzero Vandermonde determinant. Since the coefficients were uniform, the observed shares have the same distribution for every $N$. Thus they give no information about the secret.

For the fake, reduce its integers to field elements and first check that its abscissa is distinct and nonzero. Random collisions or a zero abscissa are immediately detectable and have probability $O(n/p)$; the following conclusions concern the overwhelmingly likely distinct-abscissa case.

With $r$ shares, there is always a unique degree-at-most-$r-1$ interpolating polynomial. If all shares are genuine it gives the correct secret. If one is fake, it normally gives the wrong secret, with probability $1-1/p$ conditional on a uniform fake ordinate, but the inconsistency is undetectable from those $r$ shares. The data do not certify which case has occurred.

With $r+1$ shares, genuine shares are consistent with one such polynomial. A fake is inconsistent with probability $1-1/p$, so it is usually detected as an inconsistency. However, omitting each of the $r+1$ shares in turn gives $r+1$ possible polynomials. If the data are inconsistent, their constant terms are distinct: two candidate polynomials with the same constant term agree at zero and at their $r-1$ common abscissae, hence agree identically, which would make all the data consistent. The secret is narrowed to $r+1$ possibilities, but the fake is not identified.

With $r+2$ shares, at least $r+1$ are genuine. There is a unique degree-at-most-$r-1$ polynomial agreeing with at least $r+1$ shares: two candidates would agree on at least $r$ abscissae and hence coincide. Find it by deleting each share and checking consistency. The secret is recovered uniquely, and the fake is identified unless it happens to lie on the genuine polynomial, in which case it is harmless.

Put $\xi =r/(r_0\lambda )$ and $n=n_0{\lambda }^{-2}F(\xi )$. Direct differentiation givesThus the partial differential equation reduces to an ordinary differential equation precisely when ${\lambda }^5\dot{\lambda }=C{D}_0/r_0^2$. The profile then satisfies $(\xi F^2{F}^{\prime }{)}^{\prime }=-C({\xi }^{2}F{)}^{\prime }$. Regularity and zero radial flux at the origin make the integration constant zero. Wherever $F>0$, $F{F}^{\prime }=-C\xi$, so $F^2=1-C{\xi }^2$ using $F(0)=1$. Requiring the front at $\xi =1$ selects $C=1$. Point release requires $\lambda (0)=0$, givingAlthough $F^{\prime }$ diverges at the front, $F^2{F}^{\prime }$ tends to zero, so this compactly supported profile satisfies the equation in the weak solution sense.

The compact radial cubic-diffusion profile conserves the total population:Consequently $\boxed{r_0=\sqrt{3Q/(2\pi n_0)}}$. The front radius grows as $t^{1/6}$, while the central density decays as $t^{-1/3}$. The conserved mass concentrates at the origin as $t\downarrow 0$.

Choose $\log u$ with $-\pi <\arg u<\pi$. The cut's upper and lower banks have $u=-x$, $x\in (0,1)$, and giveThe small circle about zero vanishes for $\mathrm{Re}z>0$. On the unit circle put $u=e^{i\theta }$. Since $u^2-4u+1=-2u(2-\cos \theta )$, its contribution isUsing $2-\cos \theta =1+2{\sin }^2(\theta /2)$ gives the required decomposition.

The only enclosed pole is $a=2-\sqrt{3}$; the other root $2+\sqrt{3}$ is outside. The residue theorem, including the factor $i$ in front of the contour integral, givesHere the positive real logarithm defines the power, so this expression is an entire function of $z$. The finite-interval integral $G$ is also entire, by differentiation under the integral on compact sets. Therefore $F(z)=\frac{\pi }{\sqrt{3}}(2-\sqrt{3}{)}^{z-1}-G(z)$ is an analytic continuation valid on the whole complex plane. Outside $\mathrm{Re}z>0$ it is this continuation, rather than the unregularized cut integral, that defines $F$.

Take $\theta$ as the inclination of the symmetry axis to the upward vertical, $\varphi$ as its azimuth, and $\psi$ as rotation of the body about that axis relative to the line of nodes. The kinetic energy and potential energy areThe cyclic coordinates $\psi ,\varphi$ and time independence give three conserved quantities:Their meanings are the component of angular momentum along the body axis, the component along the vertical, and the total energy.

For a vanishingly small perturbation of the upright spinning state, $L\simeq Cn$, $p_{\varphi }\simeq L$, and $E\simeq L^2/(2C)+mg\ell$. Eliminating $\dot{\varphi }$ gives the limiting effective potentialIts quadratic change near zero is $\{L^2/(8A)-mg\ell /2\}{\theta }^2$. Thus if $C^2{n}^2>4mg\ell A$, zero is a strict local minimum and a sufficiently small perturbation remains near it.

In the unstable case, the limiting energy equation becomesAt the nonzero turning point the bracket vanishes, yieldingThe approximation is the small-perturbation limit, not an assertion that arbitrary disturbances preserve the upright state's exact conserved quantities.

The map $\beta \mapsto {\omega }^{\beta }$ is strictly increasing and continuous at limit ordinals. Also ${\omega }^{\beta }\ge \beta$, so the set $S=\{\beta :{\omega }^{\beta }\le \alpha \}$ is nonempty and bounded by $\alpha$. If $\sup S$ is a successor, it is already in $S$; if it is a limit, continuity gives ${\omega }^{\sup S}={\sup }_{\beta \in S}{\omega }^{\beta }\le \alpha$. Thus $S$ has a greatest element $\beta$.

The initial segment of the well-order $\alpha$ of order type ${\omega }^{\beta }$ leaves a tail of some order type $\gamma$, giving ${\omega }^{\beta }+\gamma =\alpha$. For fixed left summand, ordinal addition is strictly increasing in its right argument, so this $\gamma$ is unique.

Maximality gives $\alpha <{\omega }^{\beta +1}={\omega }^{\beta }\omega$. Choose the least positive integer $m$ such that $\alpha <{\omega }^{\beta }m$. Then $m\ge 2$ and ${\omega }^{\beta }(m-1)\le \alpha$. If $\gamma \ge {\omega }^{\beta }(m-1)$, monotonicity of ordinal addition would give $\alpha ={\omega }^{\beta }+\gamma \ge {\omega }^{\beta }m$, a contradiction. Hence $\gamma <{\omega }^{\beta }(m-1)\le \alpha$. If $\alpha$ is not a power of $\omega$, both ${\omega }^{\beta }$ and $\gamma$ are nonzero and smaller than $\alpha$, proving decomposability.

Conversely, prove by transfinite induction that any two ordinals below ${\omega }^{\beta }$ have sum below ${\omega }^{\beta }$. For $\beta =0$ the only smaller ordinal is zero. For $\beta =\delta +1$, choose finite $m,n$ with $x<{\omega }^{\delta }m$ and $y<{\omega }^{\delta }n$. Monotonicity gives $x+y<{\omega }^{\delta }(m+n)<{\omega }^{\delta +1}$. For limit $\beta$, choose $\delta <\beta$ sufficiently large that $x,y<{\omega }^{\delta }$, and apply the induction hypothesis. Thus the nonzero indecomposable ordinals are exactly the powers of $\omega$.

A matching in a graph from $X$ to $Y$ chooses one distinct neighbour in $Y$ for each vertex of $X$. For a finite bipartite graph, the Hall marriage theorem states that such a matching exists if and only if $|\Gamma (A)|\ge |A|$ for every $A\subseteq X$. Necessity follows because the matched neighbours of $A$ are distinct members of $\Gamma (A)$.

For sufficiency use induction on $|X|$, with the empty and one-vertex cases immediate. If some nonempty proper $A$ satisfies $|\Gamma (A)|=|A|$, the induced graph on $A,\Gamma (A)$ satisfies Hall's condition. The remaining graph on $X\setminus A,Y\setminus \Gamma (A)$ does too: for $B\subseteq X\setminus A$,Inductively match both pieces and combine them. If no nonempty proper subset is tight, choose an edge $xy$ and remove its endpoints. Every nonempty subset $B$ of the remaining $X$ is proper in the original $X$, so $|\Gamma (B)|\ge |B|+1$; removing $y$ preserves Hall's condition. Match the remainder inductively and add $xy$. This proves the theorem without a flow or disjoint-path theorem.

Fix any edge $xy$. After deleting $x$ and $y$, every nonempty subset $A$ of $X\setminus \{x\}$ satisfies $|\Gamma (A)\setminus \{y\}|\ge |A|$, by the strict inequality in the question. The Hall marriage theorem gives a matching in a graph for the remainder; adding $xy$ gives a matching covering $X$ and containing the prescribed edge. The case $|X|=1$ is immediate.

Suppose a nonempty proper $A$ is tight. In every matching in a graph covering $X$, the vertices of $A$ use every vertex of $\Gamma (A)$. Hence no edge from $X\setminus A$ to $\Gamma (A)$ could occur in such a matching. The assumption that every edge occurs therefore rules out all such edges. By definition there are also no edges from $A$ to $Y\setminus \Gamma (A)$. This separates $A\cup \Gamma (A)$ from the rest, which contains the nonempty set $X\setminus A$, contradicting connectedness. Hall's inequality must therefore be strict on every nonempty proper $A$.

Take a disjoint union of $n$ single edges, each joining one vertex of $X$ to one of $Y$. Its unique matching in a graph covering $X$ contains every edge, while any singleton $A\subset X$ satisfies $|\Gamma (A)|=|A|=1$. For $n\ge 2$ this $A$ is nonempty and proper. This illustrates why connectedness was needed in part (ii).

No. In the six-cycle with cyclic vertices $1,2,\dots ,6$, every edge belongs to one of the two alternating perfect matchings. However, the disjoint edges $12$ and $45$ cannot belong to a common perfect matching: the remaining vertices $3,6$ are not adjacent. Taking $X=\{1,3,5\}$ and $Y=\{2,4,6\}$ gives the required bipartite graph counterexample.

For the first field, set $K=\mathbb{Q}(\sqrt{5},i)$. Its field extension degree is four, since $\mathbb{Q}(\sqrt{5})$ is real and adjoining $i$ doubles its degree. The polynomial $X^3-5$ is irreducible over $K$: a reducible cubic would have a root in $K$, but every root has degree three over $\mathbb{Q}$ by Eisenstein criterion, impossible by the tower law because $3\nmid 4$. Thus

For the second field, put $\alpha =\sqrt[4]{5}>0$. The splitting field is $F=\mathbb{Q}(\alpha ,i)$ and has degree eight, since $X^4-5$ is Eisenstein and $\mathbb{Q}(\alpha )$ is real. Define automorphisms $r(\alpha )=i\alpha ,r(i)=i$ and $s(\alpha )=\alpha ,s(i)=-i$. They satisfy $r^4=s^2=1$ and $srs=r^{-1}$, and give eight distinct automorphisms. Hence $\mathrm{Gal}(F/\mathbb{Q})\cong D_8$.