For $n=1$ there are no edges. Every finite tree with at least two vertices has a leaf of a graph: an endpoint of a longest simple path cannot have another neighbor, since that would either create a cycle or extend the path. Delete that leaf of a graph and its sole edge. The remaining graph is still a tree, so induction gives $n-2$ remaining edges and $\boxed{n-1}$ original edges. Alternatively the decoding construction in (i) inserts exactly $n-2$ edges and then the final edge.

A label appears in the code exactly its degree minus one times, as proved in (i). It is a leaf of a graph exactly when it never appears. ThereforeFor example the code in (ii) uses three distinct labels, so its ten-vertex tree has seven leaves of a graph.

There are ten labels. The successive deleted leaves of a graph are $3,4,5,1,6,7,2,9$, paired with the respective entries $1,1,1,2,2,2,8,8$. The final two labels are $8,10$. Thus the tree has edge setHere $ij$ denotes the unordered edge $\{i,j\}$; the last edge is written with a separator to distinguish label ten. Equivalently its adjacency lists are $1:\{2,3,4,5\}$, $2:\{1,6,7,8\}$, $8:\{2,9,10\}$, with all other vertices leaves of a graph. These lists make the constructed tree unambiguous.

Encode a labelled tree by repeatedly deleting its smallest-labelled leaf of a graph and recording its neighbor, stopping when two vertices remain. This produces a sequence of length $n-2$ with entries in $\{1,\dots ,n\}$.

Conversely, given such a sequence, at each step choose the smallest unused label not occurring in the remaining sequence, join it to the first sequence entry, delete that chosen label and the first entry, and continue. Finally join the two labels left over. A label outside the remaining sequence always exists because two more labels than entries remain. The process never uses a previously deleted label as a sequence entry. Each step attaches a new leaf of a graph to the eventual remaining graph, so backward induction shows that the result is connected and acyclic, hence a tree.

In a tree encoding, a vertex occurs once for every incident edge except the edge by which it is eventually removed, or the final surviving edge. Thus its number of occurrences is its degree minus one. The labels absent from the current remaining sequence are exactly the current leaves of a graph. Both procedures therefore choose the same smallest leaf of a graph and edge at every stage. They are inverse maps, proving the claimed bijection, including the empty sequence when $n=2$.

Use the degree-ordered orthogonal polynomials identified in (b); otherwise the printed nodes need not exist. Let ${\ell }_j$ be the degree-$n$ Lagrange interpolation polynomial with ${\ell }_j(x_i)={\delta }_{ij}$ and set $w_j={\int }_a^b{\ell }_j(x)w(x)dx$.

For any $f\in {\Pi }_{2n+1}$, polynomial division gives $f=p_{n+1}s+r$ with $\mathrm{deg}s\le n$ and $\mathrm{deg}r\le n$. Orthogonality gives $\int p_{n+1}sw=0$, while this product also vanishes at every node. The interpolation formula for $r$ then provesApply this exactness to ${\ell }_j^2$, of degree at most $2n$. It gives $w_j={\int }_a^b{\ell }_j(x{)}^{2}w(x)dx>0$, because ${\ell }_j$ is not the zero polynomial. Thus all quadrature weights are actually strictly positive, stronger than the requested nonnegativity. Here exactness is for the weighted integral defined at the start of the question.

An arbitrary orthonormal basis does not have the printed property. For example on $[-1,1]$ with $w=1$, take the usual normalized constant and linear Legendre polynomials and swap their labels $p_0,p_1$. The resulting family is still an orthonormal basis but $p_0$ has one zero, rather than zero. The necessary intended hypothesis is that $p_k$ has degree $k$, or equivalently that the basis is obtained by orthogonalizing $1,x,x^2,\dots$ in that order.

Under this hypothesis, $p_k$ is orthogonal to every polynomial of degree less than $k$. Let $t_1,\dots ,t_s$ be its sign-changing zeros in $(a,b)$ and put $q(x)={\prod }_{j=1}^s(x-t_j)$. If $s<k$, then $p_{k}q$ has a constant nonzero sign except at finitely many points: each interior sign change has been canceled, and all remaining zeros have even multiplicity or occur at endpoints. Since $w>0$, its integral cannot vanish. But orthogonality to $q$, of degree $s<k$, says that integral is zero, a contradiction. Thus $s\ge k$. Since the polynomial has degree $k$, it follows thatThis proves the requested conclusion in its standard intended setting and explains why it does not follow from the literal basis statement alone.

Assume the intended nondegenerate interval $a<b$ and real-valued continuous functions. The integral is bilinear and symmetric. Since $w>0$, it gives $⟨f,f⟩\ge 0$. If a continuous $f$ is nonzero at some point, continuity makes $f^{2}w$ strictly positive on a subinterval of positive length, so its integral is positive. Hence $⟨f,f⟩=0$ forces $f=0$, proving positive definiteness. Orthogonality means $\boxed{{\int }_a^{b}f(x)g(x)w(x)dx=0}$. If $a=b$, the displayed integral is identically zero and is not an inner product on the stated function space; that degenerate case must be excluded.

Suppose $u,v\in U_n$ both attain the minimum distance $d$. Apply (b) to $x-u$ and $x-v$:The midpoint belongs to $U_n$, so its squared distance is at least $d^2$. Thus $\Vert u-v{\Vert }^2\le 0$, forcing $\boxed{u=v}$. Existence will also follow constructively in (d)(i).

Expand using the inner product. The two cross terms cancel:Adding proves $\boxed{\Vert x-y{\Vert }^2+\Vert x+y{\Vert }^2=2(\Vert x{\Vert }^2+\Vert y{\Vert }^2)}$, for real or complex inner products.

A best approximation to $x$ from $U_n$ is an element $u_{\ast }\in U_n$ satisfying $\boxed{\Vert x-u_{\ast }\Vert =\underset{u\in U_n}{\inf }\Vert x-u\Vert }$. This is a minimum over the specified approximation subspace, not over all of $H$.

For a fixed $\lambda <{\lambda }_0$, the likelihood ratio against the null isstrictly increasing in $S={\sum }_i{x}_i$. The Neyman–Pearson critical region is therefore an upper tail in $S$, and its null threshold depends only on the desired size, not on which $\lambda <{\lambda }_0$ was chosen. Thus the same test is uniformly most powerful for the entire one-sided alternative.

Under the null $S\sim \mathrm{Gamma}(n,{\lambda }_0)$ with the second parameter interpreted as rate. Its continuous distribution permits the exact thresholdUnder any fixed alternative its rejection probability is $\boxed{Q(\lambda )=1-F(c_{\alpha };n,\lambda )}$. Applying the lemma separately to each such $\lambda$ shows that every level-$\alpha$ test has power at most this value there. The constructed test attains the bound for all $\lambda <{\lambda }_0$ simultaneously.

For a rejection function $\phi (x)\in [0,1]$, its power is $\beta (\theta )={\mathbb{E}}_{\theta }\phi (X)$. A test has level at most $\alpha$ if ${\sup }_{\theta \in H_0}\beta (\theta )\le \alpha$; its size is that supremum. In a simple null the significance probability is just the rejection probability under that null.

For two simple hypotheses with joint sample densities $f_0,f_1$, the Neyman–Pearson lemma states that a test rejecting where $f_1>k{f}_0$, accepting where $f_1<k{f}_0$, and randomizing if necessary on equality to have size $\alpha$, is most powerful among level-$\alpha$ tests. Let ${\phi }_{\ast }$ be that test and $\phi$ any competitor. Pointwise,Integration givessince $k\ge 0$, the first test has size $\alpha$, and the other has size at most $\alpha$. This proves the claimed power bound, allowing null-density-zero regions as well. Equality implies agreement away from the likelihood-ratio boundary, up to null sets, when the inequalities are strict.