So here I have 3 tree-related questions.
1) Let $n\geq2$ and let $d_1 ≤d_2 ≤···≤d_n$ be a sequence of integers. Show that there is a tree with degree sequence $d_1,d_2,...,d_n \Leftrightarrow \sum d_i =2n−2.$
2) Let $T$ be a tree with $n$ vertices. Assume each vertex of T has degree 1 or $d$ (for some $d > 1$). Find a formula for the number of vertices of degree 1 in $T$.
3) Let $G$ be a binary tree (a rooted tree in which every vertex has at most two children) with $t$ leaves. How many vertices of degree 3 does $G$ have?
Progress with 1: One implication is simple by the Handshake Lemma. The other is a bit more tricky. I found that the sum of the edges, $| E |$ is $\frac{2n-2}{2} = n - 1 = |V| - 1$ by the Handshake Lemma. But I cannot see a clear way of showing that the graph is connected and thus a tree.
Progress with 2: I can't see a clear path forward with this at all. All I know is that the number is at least 2, as the graph is a tree, but I assume I am looking for a number related to $n$ and $d$ rather than bounds...
Progress with 3: Just noticed a few facts. Each binary split gives rise to a vertex of degree 3, and the least height of the binary tree before we have $t$ leaves is $\lceil{log_2(t)}\rceil$.Assuming all splits are binary, level $i$ would give rise to $2^i$ vertices of degree 3 and the total sum of these would be at most $\displaystyle\sum_{i=1}^{\lceil log_2(t)\rceil} 2^i$. I think...
Thank you for your continued help, stackexchange!
Some HINTS:
In the first problem you can use induction on $n$. Let $d_1\le d_2\le\ldots\le d_n$ be a sequence of positive integers such that $$\sum_{i=1}^nd_i=2n-2\;.$$ First note that if $\sum_{i=1}^nd_i=2n-2$, then $d_1=1$, and $\sum_{i=2}^nd_i=2n-3$. And $2(n-1)>2n-3$, so we must also have $d_2=1$ and hence $\sum_{i=3}^nd_i=2n-4$. We now have $n-2$ integers, $d_3,\ldots,d_n$, whose sum is $2(n-2)$, so either $d_3=\ldots=d_n=2$, or $d_n>2$.
In the second problem suppose that $T$ has $\ell$ leaves and $n-\ell$ vertices of degree $d$; then the sum of the degrees of the vertices of $T$ is $\ell+d(n-\ell)$. On the other hand, this sum must be twice the number of edges, and $T$ has $n-1$ edges, so $\ell+d(n-\ell)=2n-2$. Now just solve for $\ell$ in terms of $d$ and $n$.
In the third problem suppose that $v$ is a vertex of degree $2$ other than the root; then $v$ has a parent $u$ and a single child $w$. We can remove $v$ and make $w$ a child of $u$ without changing the number of leaves or the number of vertices of degree $3$. Repeating this process a finite number of times leaves us with a tree $G'$ whose vertices are either leaves, vertices of degree $3$, or the root. Moreover, $G'$ still has $t$ leaves, and it has the same number of vertices of degree $3$ as $G$. Let $m$ be the number of vertices of degree $3$. Then either the root has two children, in which case $G'$ has $t+m+1$ vertices, or it has only one child, in which case it’s a leaf, and $G'$ has $t+m$ vertices. In each case you know how many vertices $G'$ has of each possible degree, so you can use the same kind of analysis as in the second problem to compute $m$ in terms of $t$.