Bounding the number of monovalent vertices in a graph satisfying a certain condition 
Show that a graph with exactly one vertex of degree $i$ : $2\le i \le m$ and $k$ other vertices (which are monovalent) satisfies $$\left\lfloor\frac{m+3}2\right\rfloor \le k\;.$$

Here is my current approach. I want to a construct a graph of minimal $k$ - to do this I need to make sure that all the all the other vertices of degree $i$ connect to the vertex of degree $m$, and that the other vertices of degree $m-1$, $m-2$, ... share the largest number of vertices that won't result in a double. Here is my current construction.
Start with a vertex of degree $m$ $v_0$. choose some $v$ adjacent to that vertex, $v_1$. Connect it to $m-2$ of the other vertices giving it degree $m-1$ and creating $m-2$ vertices of degree $2$. At the next step, choose another of the vertices of degree $2$, call it $v_3$. connect it to $m-4$ vertices of degree $2$, leaving $1$ vertex of degree $2$, and creating $m-4$ vertices of degree $3$.
This produces a sequence of graphs $G_n$, where each graph contains exactly one vertex of degree $1,\dots ,n+1$ and degree $m,\dots ,(m-n)+1$.
Now at some point, we will reach an $i$ s.t $m-i = i+1$, at which point we will have two duplicate vertices. We then only have to move at most $i$ edges in order to get a graph with the "minimal number" of monovalent vertices satisfying this property.
Problem is I can't prove this graph is minimal, and I can't figure out how to get the bound to arise from this construction. 
 A: The idea of this problem is to look at how many vertices we need to add such that the resulting degree sequence is actually realizable as a simple graph. You can draw a few examples yourself and you will quickly realize that the vertices of degree $2\le i \le m$ alone is not realizable as a graph. To produce a graph, we must add a number of monovalent vertices. Let us take a look at how many monovalent vertices we must add to produce a proper graph then. 
Suppose a graph with vertices of degree $i:\ 2\le i \le m$ along with $k$ monovalent vertices exist. Then the degree sequence of this graph
$$(m, m-2, \cdots, 2, \underbrace{1, \cdots, 1}_k)$$
must satisfy the Erdős-Gallai Theorem, i.e. we must have
$$\sum^{i}_{j=1}d_j\leq i(i-1)+ \sum^n_{j=i+1} \min(d_j,i)$$
for $1\le i \le n$ where $n$ is the number of vertices.
The idea is to examine the associated inequalities at their "weakest" point. 
Consider the first $m-1$ vertices. Their associated numbering in the sequence is
$$\begin{matrix}d_i=&m & m-1 & \cdots & 3 & 2\\i= & 1 & 2 & \cdots & m-2 & m-1 \end{matrix}$$
The point at which the latter sum begins to increase less rapidly is precisely when $i \ge d_{i+1}$ which first happens at $i=\lfloor\frac{m+1}{2}\rfloor$ and that is the point at which we want to take our inequality. To avoid tedious floor functions, I will work with even and odd cases separately (actually, I will do even and leave odd to you). 
Let $m=2\ell$. Then the inequality can be written as
$$\sum_{j=1}^\ell d_j \le \ell(\ell-1) + \sum_{j=\ell+1}^{m-1}(d_j) + k$$
Evaluating the sums gives
$$\sum_{j=1}^\ell d_j = m + \cdots + (m-\ell +1) = \frac{(2\ell)(2\ell+1)}{2} - \frac{(\ell + 1)(\ell)}{2}$$
$$\sum_{j=\ell+1}^{m-1}(d_j) = (m-\ell) + \cdots + 2 = \frac{(\ell + 1)(\ell)}{2} - 1$$
and putting it all together
$$\frac{(2\ell)(2\ell+1)}{2} - \frac{(\ell + 1)(\ell)}{2} - \frac{(\ell + 1)(\ell)}{2} + 1 - \ell(\ell-1) \le k$$
after simplification, you yield
$$\ell(2\ell + 1) - (\ell-1)\ell - (\ell + 1)\ell + 1 \le k$$
$$\ell + 1 = \frac{2\ell+2}{2} = \left\lfloor\frac{m + 3}{2}\right\rfloor\le k$$
The case for odd $m$ follows similarly and I will leave that proof to you.
