Past exam of the mathematics course of the University of Cambridge / 2017 / ii / Paper 1

For an odd prime number $p$, the Legendre symbol is zero when $p\mid a$, one when $a$ is a nonzero quadratic residue modulo $p$, and minus one otherwise. The number-theoretic Gauss lemma says that, for $p\nmid a$, $(a/p)=(-1{)}^r$, where $r$ counts those least positive residues of $a,2a,\dots ,(p-1)a/2$ exceeding $p/2$.

For $a=2$, the residues are simply $2,4,\dots ,p-1$, so $r=(p-1)/2-\lfloor p/4\rfloor$. Examining the four odd residue classes modulo eight givesNow $2^m\equiv -1(\mathrm{mod}p)$ and $p$ is odd. The multiplicative order $d$ of $2$ divides $2m$ but not $m$. Since $m$ is a power of two, every proper divisor of $2m$ divides $m$, whence $d=2m$. Lagrange's theorem for finite groups gives $2m\mid p-1$. Because $m\ge 4$, this implies $p\equiv 1(\mathrm{mod}8)$, so the supplementary law just proved gives $(2/p)=1$. By Euler's criterion, $2^{(p-1)/2}\equiv 1(\mathrm{mod}p)$, and consequently $2m\mid (p-1)/2$. Therefore

The Liouville approximation theorem states that an irrational algebraic number $\alpha$ of degree $d\ge 2$ satisfies $|\alpha -a/b|\ge C_{\alpha }{b}^{-d}$ for all integers $a$ and $b\ge 1$, for some $C_{\alpha }>0$. The constant is independent of the rational approximation.

The required condition is infinitely many of the coefficients equal one. If only finitely many do, the series is a finite sum of rational numbers. Conversely let $\alpha$ be the sum with infinitely many nonzero terms. Its truncation $s_N$ has denominator dividing $q_N=10^{N!}$. For $N\ge 2$, its strictly positive tail satisfiesIf $\alpha =a/b$ were rational, the distinct fractions $\alpha ,s_N$ would have distance at least $1/(b{q}_N)$, contradicting the tail bound for large $N$. Thus $\alpha$ is irrational. If it were algebraic of fixed degree $d$, apply the Liouville approximation theorem to $s_N$. Even if its reduced denominator is smaller than $q_N$, the lower bound is at least $C_{\alpha }{q}_N^{-d}$. The displayed upper bound contradicts this as $N\to \infty$. HenceThe coincidence $0!=1!$ changes only the first rational contribution and has no effect on this criterion.

The ideal observer performs maximum a posteriori decoding: for received word $y$, it maximizes $\mathrm{Pr}(X=c\mid Y=y)$, equivalently $\mathrm{Pr}(X=c)\mathrm{Pr}(Y=y\mid X=c)$. Maximum-likelihood decoding maximizes the latter conditional likelihood alone. Minimum-distance decoding minimizes the Hamming distance $d(c,y)$. Ties may be resolved arbitrarily among maximizers.

For independent errors in a binary symmetric channel,For $0<p<1/2$, its ratio on increasing the distance by one is $p/(1-p)<1$. Thus maximum-likelihood decoding and minimum-distance decoding select exactly the same codewords. At the allowed endpoint $p=0$, they agree on a possible observation $y\in C$; impossible observations have zero likelihood for every codeword, so an arbitrary maximum-likelihood tie rule need not agree with minimum distance. This qualification is needed for the literal assumption $p<1/2$.

For the specified observation, the Hamming distances from 000 and 111 are two and one. Their likelihoods are $3/64$ and $9/64$, respectively. After multiplying by the priors, their joint probabilities are $12/320$ and $9/320$, so their posterior probabilities are $4/7$ and $3/7$. Therefore

Let a deterministic finite automaton recognizing the regular language have states $Q$, start state $q_0$, accepting states $F$, and transition function $\delta$. Construct a context-free grammar with one nonterminal $A_q$ for every state, start symbol $A_{q_0}$, and productionsInduction on the length of a word shows that $A_q$ derives $w{A}_r$ exactly when the automaton reaches $r$ from $q$ after reading $w$. The terminal production can then end the derivation precisely at an accepting state. Thus the grammar generates exactly the recognized language, proving every regular language is a context-free language. This is actually a right-linear grammar, a special case of a context-free grammar.

Treat the fixed letters $a_1,\dots ,a_n$, the empty-language and empty-word symbols, and the punctuation of expressions as a finite token alphabet. In the usual syntax allowing parentheses, union, concatenation, and star, the following context-free grammar generates exactly the syntactically valid regular expressions:Structural induction proves that every generated string is an expression and that every expression has a derivation. Grammar ambiguity does not affect the context-free language assertion.

If the language of these expressions were a regular language, its intersection with the regular token language consisting of some opening parentheses, then $a_1$, then some closing parentheses would be regular. That intersection is exactlyThe pumping lemma for regular languages contradicts regularity: a sufficiently long opening-parenthesis prefix forces a pumpable segment wholly within that prefix, and pumping it changes the two parenthesis counts unequally. Hence the expression syntax is context-free but not regular. This conclusion concerns the strings describing expressions, not the languages those expressions denote; it uses the usual concrete syntax with arbitrary nested parentheses.

The comparison is a nested-model F-test of the three time-by-diet interaction coefficients, with null hypothesis that all are zero. The reduced linear regression model has a common time slope and four diet-specific intercepts; the full model permits four slopes. It has eight fitted coefficients and $579-8=571$ residual degrees of freedom.The rounded sums of squares give the displayed approximation; the software reports $F=16.824$ using unrounded values. The quoted p-value $1.744\times 10^{-10}$ gives overwhelming evidence against equal log-weight growth slopes across diets under the normal linear model assumptions. Thus reject the common-slope hypothesis. Because repeated measurements on the same chicken may be correlated, the exact reference distribution requires independent, homoscedastic Gaussian errors; the displayed ordinary regression output by itself does not establish that assumption.

A residual-versus-fitted plot for the untransformed fit places $e_i=y_i-{\hat{y}}_i$ on the vertical axis and ${\hat{y}}_i$ on the horizontal axis. A fan-shaped cloud, with larger residual spread at larger fitted weight, suggests heteroscedasticity and approximately multiplicative errors. A logarithmic transformation may stabilize this spread when the conditional standard deviation is roughly proportional to the mean.

One can also use the scale-location plot of $\sqrt{|r_i|}$ against fitted values, where $r_i$ is a standardized residual. A systematic rise suggests nonconstant error variance. Neither plot proves that taking logarithms is sufficient: diagnostics of the transformed fit should be checked as well, and dependence between repeated chicken measurements is a separate issue.

The dashed curves are contours of constant Cook's distance, labelled 0.5 and 1, in the plot of standardized residual against regression leverage. Writing $h_{ii}$ for the diagonal of the hat matrix, $s^2$ for the residual variance estimate, and $p=8$ for the number of fitted coefficients,Thus a contour $D_i=d$ has $r_i=\pm \sqrt{dp(1-h_{ii})/h_{ii}}$. On the actual PDF plot, observation 579 has leverage about 0.084 and standardized residual about $-8$, lying beyond the $D=0.5$ contour and below $D=1$ in influence magnitude, approximately $D\simeq 0.7$ to $0.8$ from the plotted coordinates. It is unusually light relative to its fitted log-weight and potentially influential because deleting it can materially change fitted coefficients. It warrants checking, not automatic deletion. The solid smooth red curve is distinct from the dashed Cook's distance contours.

For nonnegative insect density assume $N_0>0$. Substitution of $N=e^{\alpha t}R$ gives $R_t=D{e}^{2\alpha t}(R^2{R}_x{)}_x$, so chooseThen ${\tau }^{\prime }=D{e}^{2\alpha t}>0$ and the porous medium equation is $R_{\tau }=(R^2{R}_x{)}_x$. Its total mass is conserved when the flux vanishes at infinity. For the mass-preserving similarity solution, direct differentiation givesOn the positive support, integrating once with zero boundary flux gives $F^2{F}^{\prime }=-\xi F/4$ and hence $F^2=({\xi }_0^2-{\xi }^2)/4$. The semicircle mass integral is $\pi {\xi }_0^2/4=N_0$, confirming the profile and its symmetric compact support.

The front is at $|x|={\xi }_0{\tau }^{1/4}$. When $\alpha <0$, $\tau (t)$ increases towards $D/(2|\alpha |)$, so the supremum of the distance reached isIt is approached as $t\to \infty$, rather than attained at a finite time. If $N_0=0$, the nonnegative solution is identically zero and the corresponding distance is zero.

There is an important convention issue in the printed statement. The ordinary Cauchy principal value exists only for $n=1$. Closing the Fourier contour in the lower half-plane, with a small indentation above the real-axis pole, givesEquivalently, the odd cosine contribution cancels and the Dirichlet integral ${\int }_0^{\infty }\sin x/xdx=\pi /2$ supplies the imaginary part.

For $n\ge 2$, the paired integrand near zero is $2\cos x/x^n$ if $n$ is even and $-2i\sin x/x^n$ if $n$ is odd. Its leading even power is nonintegrable: $x^{-n}$ in the first case and $x^{1-n}$ in the second. Thus the ordinary principal value diverges for every $n>1$.

If the intended convention is the Hadamard finite-part integral, define it consistently by distributional differentiation,Integration by parts in this distributional pairing, or regularized Fourier transformation, then givesThe distinction is essential: subtracting the divergent local Taylor terms supplies a finite part, but symmetric exclusion alone does not.

Assume the holonomic constraints have linearly independent gradients, so their common level set is locally a smooth constraint manifold parametrized by $q_1,\dots ,q_n$. The multiplier form of the Euler-Lagrange equations isAt fixed time ${\sum }_A{\partial }_A{f}_{\alpha }{\partial }_i{x}_A=0$. The chain rule for the reduced Lagrangian givesConversely, if these reduced equations hold, the Cartesian Euler-Lagrange residual annihilates every tangent direction. Linear independence of the constraint gradients implies that it is a linear combination of those gradients, giving the required Lagrange multipliers. This proves the local equivalence, including time-dependent constraints; singular constraints would need separate analysis.

For the bead, $\dot{y}=f^{\prime }(x)\dot{x}$, soThe autonomous conservation of energy gives $E=\frac{1}{2}(1+f^{\prime 2}){\dot{x}}^2$. If $E>0$, the motion has a fixed sign $s=\mathrm{sgn}\dot{x}$ andThe integral is the signed arc length divided by the constant speed, and is locally invertible. The special solution $E=0$ is a stationary bead, for which writing time as a function of its unchanging position is not meaningful.

For comoving galaxies their relative comoving vector $\mathbf{\chi }$ is constant, and the physical displacement is $\mathbf{r}(t)=a(t)\mathbf{\chi }$, where $a$ is the scale factor. Differentiating gives the Hubble lawPeculiar velocity relative to this comoving frame is excluded in this relation.

Transport a wave crest between neighbouring comoving observers separated by a small physical distance $d\ell$. Their recession speed is $Hd\ell$, while the light travel time is $dt=d\ell /c$ to first order. The local Doppler shift therefore changes its wavelength by $d\lambda /\lambda =Hdt$. Multiplying these infinitesimal shifts along the ray, or integrating their logarithms, yieldsThe use of the local first-order Doppler law is exact in the limit of infinitesimal steps: the accumulated second-order errors tend to zero. A single special-relativistic recession velocity assigned to widely separated galaxies would not justify this cosmological redshift relation.

A linear code of length $n$ and rank $k$ is a $k$-dimensional linear subspace of ${\mathbb{F}}_2^n$. The Hamming weight of a vector counts its nonzero coordinates. Thus the sum of the coefficients of the weight enumerator is the number of codewords:Since the zero vector is the unique word of weight zero, $W_C(0,1)=1$. Symmetry of the enumerator therefore implies $W_C(1,0)=1$. Conversely $W_C(1,0)=1$ means that the all-one vector $1$ belongs to $C$. Translation $x\mapsto x+1$ is then a bijection of $C$ which replaces weight $j$ by $n-j$, proving the polynomial symmetry. For length zero the same conclusion holds with the unique empty vector.

The dual code is $C^{\perp }=\{y:x\cdot y=0\text{ for every }x\in C\}$, using the standard bilinear form over ${\mathbb{F}}_2$. If $y\in C^{\perp }$, each summand of the character sum equals one. Otherwise choose $x_0\in C$ with $x_0\cdot y=1$; replacing $x$ by $x+x_0$ permutes the summands and reverses their sign. The sum equals its own negative and must be zero. ConsequentlyThis is character orthogonality for the additive group of the code.

For any vector $y\in {\mathbb{F}}_2^n$, use its Hamming weight $w(y)=\#\{j:y_j=1\}$. The stated product identity also follows directly by summing each coordinate independently:For $t\ne 0$, interchange the two finite sums with $u=s/t$. Character orthogonality evaluates the inner sum over codewords, whereas the product identity evaluates the sum over all binary vectors. ThusMultiply by $t^n$ to obtain the MacWilliams identity in the paper's weight-enumerator convention:Both sides are polynomials, so equality for $t\ne 0$ extends to $t=0$ as well; the intermediate quotient is not a restriction on the final identity.

A deterministic finite automaton is described by finite state and alphabet label lists, one initial state label, an accepting-state bit mask, and a finite transition table. Keep each label in increasing order and list transitions lexicographically by the actual state and alphabet labels. This retains arbitrary finite subsets of the permitted labels, rather than assuming they are consecutive.

The prime-exponent encoding of a finite list gives an explicit Gödel encoding for a list $(a_0,\dots ,a_{r-1})$ of nonnegative integers:where $p_i$ is the $i$th prime number. Encode the descriptor as a list beginning with the numbers of states and alphabet symbols, followed by their sorted labels, the start label, the accepting mask, and all transition destinations. The lengths are then known during decoding.

Unique prime factorization recovers the list and hence the automaton. Reject an integer if the prescribed prime exponents are missing, additional primes occur, the list lengths disagree, state or alphabet labels repeat, the initial state or a transition target is absent, or the mask is out of range. These are effective finite checks. Thus every automaton has an integer code, valid codes are decidable, and the transition system of a coded automaton is computable. Invalid integers may be excluded explicitly or assigned a fixed empty-language automaton.

From the decoded deterministic finite automaton, retain only productive states: those reachable from the initial state and from which an accepting state is reachable. Both sets are computable by finite graph search. Its regular language is infinite precisely when this productive directed graph contains a directed cycle.

Indeed, a cycle on a route from the start to acceptance can be repeated arbitrarily often, giving accepted words of different lengths. Conversely an accepted path of length at least the number of productive states repeats one such state and gives a productive cycle. Therefore absence of cycles bounds every accepted length strictly below that number. Cycle detection is a finite algorithm, proving that finiteness of the accepted language is decidable.

When it is finite, enumerate every word of length less than the number of states and simulate acceptance, then count the accepted words. This includes the empty word. Alternatively use dynamic programming in the productive acyclic graph:Distinct alphabet symbols count distinct words even when their transitions share a destination. The result is $N(q_0)$, or zero if the start state is not productive. Validity of the encoding is checked first, so the set of valid finite-language codes is recursive set.

Under the binomial distribution model's assumption of independent games with a common win probability $p$, the probability of winning a match isThis is also the cumulative distribution function $F_{6,6}(p)$ of a Beta distribution with parameters $(6,6)$: differentiation of the binomial tail gives $h^{\prime }(p)=11!p^5(1-p{)}^5/(5!{)}^2$, and $h(0)=0$. In particular $h$ is strictly increasing on $(0,1)$ and maps $[0,1]$ bijectively onto itself.

The new match probability is ${\tilde{P}}_{ab}=h(P_{ab})$, while the desired linear predictor remains the game-level log odds. Therefore the link function isIts endpoint values are $-\infty$ and $+\infty$. This is not the ordinary match-level log odds link: it first recovers the underlying game probability. Symmetry of the binomial tail gives $h(1-p)=1-h(p)$, hence $g(1-u)=-g(u)$, as required by swapping the players. Dependence or varying game probabilities within a match would invalidate the stated binomial-tail conversion.

For $\mathrm{Re}s>1$, expand $(e^t-1{)}^{-1}={\sum }_{n\ge 1}{e}^{-nt}$. Absolute integrability, bounded near zero by a constant times $t^{\mathrm{Re}s-2}$, permits termwise integration. The Gamma function integral then givesSpecify the Hankel contour to run from the negative real axis below the cut towards zero, circle zero counterclockwise with fixed radius $0<r<2\pi$, and return above the cut. Take $-\pi <\arg t<\pi$. The circle excludes every nonzero pole $2\pi i\mathbb{Z}$ of the denominator. For $\mathrm{Re}s>1$ its radius can shrink to zero, and the lower and upper rays give respectively $-e^{-i\pi s}\Gamma (s){\zeta }_R(s)$ and $e^{i\pi s}\Gamma (s){\zeta }_R(s)$. By the Gamma reflection formula,away from integer $s$ in that half-plane, with limiting equality at the removable points.

With the circle radius kept fixed, the contour integral is an entire function of $s$: the rays decay exponentially and converge locally uniformly, and the circular part stays away from zero. Multiplication by $\Gamma (1-s)$ is analytic for $\mathrm{Re}s<1$ and meromorphic globally. The apparent singularities at positive integers $s\ge 2$ are removable because the integral vanishes there and it already agrees with the original analytic zeta function nearby. Only $s=1$ remains a simple pole. Thus this constructs the meromorphic continuation to the whole plane and an analytic continuation on $\mathbb{C}\setminus \{1\}$. Keeping the circular segment is essential when the integral is not locally integrable at zero.

At $s=-1$ the two rays cancel, since $t^{-2}$ is single-valued. The Laurent expansionshows that the residue of $t^{-2}/(e^{-t}-1)$ is $-1/12$. Since $\Gamma (2)=1$, the residue theorem gives

Differentiate the Friedmann equation and use energy conservation to obtain $\dot{H}=-4\pi G(\rho +P/c^2)$ on the expanding branch, where $H\ne 0$. Since $\ddot{a}/a=\dot{H}+H^2$,For pressureless matter, conservation gives ${\rho }_M={\rho }_{M0}{a}^{-3}$. In terms of the specified cosmological density parameters, flatness implies ${\Omega }_M+{\Omega }_{\Lambda }=1$, andSet $b=a^{3/2}$ and take ${\Omega }_M>0$. Then $\dot{b}=\frac{3}{2}{H}_0\sqrt{{\Omega }_M+{\Omega }_{\Lambda }{b}^2}$. Integrating with the Big Bang at $t=0$ givesFor another time origin replace $t$ by $t-t_B$. The cosmological constant has effective density ${\rho }_{\Lambda }=3H_0^2{\Omega }_{\Lambda }/(8\pi G)$. Equality with the matter density means $a^3={\Omega }_M/{\Omega }_{\Lambda }$, soIf ${\Omega }_M=0$, the expanding solution is pure exponential de Sitter scale factor in flat slicing and there is no finite matter-density equality time or dust Big Bang; the stated hyperbolic-sine formula presumes a nonzero dust component.

The completeness theorem for propositional logic, together with soundness, states $S⊢\phi$ if and only if $S\models \phi$. In particular, an inconsistent set of formulae has a finite formal proof of contradiction. Such a proof uses only finitely many assumptions, yielding the propositional compactness theorem: if every finite subset of $S$ is satisfiable, then $S$ is satisfiable.

The decidability theorem for propositional logic concerns theoremhood of a formula, or entailment from a finite list of premises. Formulae involve finitely many variables, so their valuations can be tested by a finite truth table; completeness identifies semantic validity with provability. Equivalently, dovetail effective proof enumeration with the finite search for a countervaluation: completeness ensures that one succeeds. This is not a decidability claim for consequences of an arbitrary noncomputable infinite theory.

An infinite collection of distinct tautologies is a finitary set of formulae, since its deductive closure equals that of the empty set. By contrast, the set of independent variables $\{p_i:i\ge 1\}$ is not finitary. If a finite set $T$ had the same closure, it would mention only finitely many variables. It is satisfiable because it is a consequence of the all-true model of the $p_i$; changing an unmentioned $p_j$ to false preserves $T$ and contradicts $T\models p_j$.

Under the final hypothesis, $A\cup B$ has no model. The propositional compactness theorem gives finite $A^{\prime }\subset A$, $B^{\prime }\subset B$ with $A^{\prime }\cup B^{\prime }$ inconsistent. Any valuation satisfying $A^{\prime }$ cannot satisfy $B$, because it would then satisfy $B^{\prime }$; by the exactly-one hypothesis it must satisfy $A$. The reverse implication holds by inclusion. Thus $A$ and $A^{\prime }$ have identical models, and similarly $B$ and $B^{\prime }$. Completeness gives identical deductive closures, proving

Let $v_1\cdots v_r$ be a longest path in the finite simple graph. Every neighbour of either endpoint lies on it. Among indices $1\le i<r$, consider those with edges $v_1{v}_{i+1}$ and those with edges $v_i{v}_r$. Their cardinalities are the endpoint degrees, whose sum is at least $n\ge r$, exceeding the $r-1$ available indices. They intersect, producing the cycleEvery connected component has at least $\delta (G)+1>n/2$ vertices, so the graph is connected. If $r<n$, an edge joins a vertex outside this cycle to it, and breaking the cycle there gives a longer path, a contradiction. Hence $r=n$ and this is a Hamilton cycle, proving Dirac theorem.

The complete graph $K_4$ is planar, has chromatic number four and a Hamilton cycle. Adding one leaf attached to one of its vertices preserves planarity and chromatic number four but prevents a Hamilton cycle, since a leaf has degree one.

For the last claim, the given plane embedding has all vertices on the outer cycle. Add noncrossing diagonals until its polygonal interior is triangulated. A triangulated polygon has a vertex incident with only its two boundary neighbours: for example the dual graph of its triangles is a tree and a leaf triangle supplies an ear. Remove this vertex. Inductively three-colour the smaller triangulated polygon, starting with a triangle. The removed vertex's neighbours are adjacent and have different colours, so it can receive the third. Restriction to the original graph givesThis uses the specified embedding, not the false assertion that every planar Hamiltonian graph is three-colourable; $K_4$ is already a counterexample to that broader assertion.

A splitting field of a nonzero polynomial $f$ over $K$ is an extension in which $f$ splits into linear factors and which is generated over $K$ by all its roots. For a constant nonzero polynomial the splitting field is $K$; the zero polynomial does not have a root-generated splitting field in this standard definition.

Given two splitting fields $L,L^{\prime }$, enumerate the roots generating $L$ and extend a $K$-embedding one root at a time. If an embedding is defined on $K({\alpha }_1,\dots ,{\alpha }_j)$, the minimal polynomial of the next root divides $f$ over that field. Its image under the embedding therefore divides $f$ over the corresponding subfield of $L^{\prime }$, and has a root in $L^{\prime }$. The quotient construction $K(\alpha )\cong K[t]/(m_{\alpha })$ extends the embedding to that root. The polynomial need not be a separable polynomial.

At the end this gives a $K$-embedding $L\to L^{\prime }$. It sends the distinct roots of $f$ injectively to its roots, hence permutes the finite set of distinct roots and contains every root in its image. Since these generate $L^{\prime }$, the embedding is onto. Thus the splitting field is unique up to a (K)-isomorphism.

The quartic is irreducible by Eisenstein criterion at two, so its Galois group is transitive on its four roots. Its discriminant is $1616=16\cdot 101$, so five and seven are unramified primes for the polynomial. The squarefree factorizations areThe cubic modulo five has no root in ${\mathbb{F}}_5$, hence is irreducible. The quadratic modulo seven has discriminant five, a nonsquare there. The Frobenius cycle type theorem therefore supplies a three-cycle and a transposition in the group.

Transitivity implies that its order is divisible by four, and the three-cycle implies divisibility by three. Its order divides $24$, so it is $12$ or $24$. The only subgroup of index two in $S_4$ is $A_4$: an index-two subgroup is the kernel of a group homomorphism of a nontrivial homomorphism to $C_2$, and all transpositions are conjugate and generate $S_4$, forcing this homomorphism to be the sign. The exhibited transposition excludes $A_4$. Hence

Modulo three, the quintic has no linear factor: its value is $-1$ at every element of ${\mathbb{F}}_3$. The monic irreducible quadratics over this field are $t^2+1$, $t^2+t+2$ and $t^2+2t+2$. Division leaves respectively $-1$, $t-1$ and $t-1$, all nonzero. A reducible quintic has a factor of degree at most two, so it is irreducible modulo three and therefore over $\mathbb{Q}$. Its Galois group is transitive on five roots.

Modulo two its squarefree factorization isBoth factors are irreducible, so the Frobenius cycle type theorem gives an element that is a disjoint transposition times a three-cycle. Cubing it gives a transposition.

The prime-degree transposition criterion can be proved here: a transitive subgroup of prime degree containing a transposition is the whole symmetric group. Construct a graph on the five roots whose edges are the pairs swapped by all conjugates of this transposition. The group acts transitively on vertices and permutes connected components, so all component sizes are equal and divide five. An edge rules out size one; the graph is connected. Edge transpositions of any connected graph generate the full symmetric group, for instance by transporting swaps along a spanning tree. All belong to the Galois group, provingThe prime-degree condition is essential to the short transposition argument.

In an irreducible complex group representation $\rho$, every $\rho (z)$ for $z$ in the center of a group commutes with the entire representation. Schur lemma therefore gives $\rho (z)={\lambda }_{z}I$. Faithfulness makes $z\mapsto {\lambda }_z$ an injective homomorphism $Z(G)\to {\mathbb{C}}^{\times }$.

Its image is a finite subgroup. If its order is $m$, Lagrange's theorem for finite groups shows that every element is an $m$th root of unity. These roots form a cyclic group, and every subgroup of a cyclic group is cyclic. HenceBoth irreducibility over the algebraically closed field and faithfulness are used: scalar action alone would not embed the centre.

Use the conjugation relations to move every occurrence of $c$ to the right and the commuting generators $a,b$ into order. Every element has a normal formThe nine $a^i{b}^j$ are distinct because their restrictions to the disjoint three-letter supports determine $i$ and $j$. Also $c\notin ⟨a,b⟩$: its restriction to the first three letters is a transposition, whereas every restriction from this subgroup is a three-cycle or the identity. Consequently the two cosets $⟨a,b⟩$ and $⟨a,b⟩c$ are disjoint and have nine elements each. Thus $|E|=18$.

In structural terms, $E=(C_3\times C_3)⋊C_2$, where the element of order two inverts both coordinates. This is a generalized dihedral group. The normal-form count also proves that the listed relations are a complete presentation, rather than merely some relations holding in the permutation group.

Let $A,B$ be the stated diagonal matrices and $C$ the interchange matrix. Since ${\epsilon }^3={\eta }^3=1$, direct matrix multiplication givesThe complete presentation established by the preceding normal-form argument therefore defines a group homomorphism $\rho :E\to {\mathrm{GL}}_2(\mathbb{C})$. More explicitly, setMultiplication of normal forms uses $c{a}^i{b}^j=a^{-i}{b}^{-j}c$, and the matrices obey exactly the same rule, so this is well-defined and multiplicative. It is the required complex group representation.