${x\choose 2}+{n-x\choose 2} \leq {n-1\choose 2}$ In a proof, the author states that it is clear that:
Given $x\geq 1$ and $ n-x \geq 1$ and finally also $n\geq 2$
$${x\choose 2}+{n-x\choose 2} \leq {n-1\choose 2}$$
This is not immediately clear to me. Of course, If I have $n$ objects and I split them up in $x$ and $n-x$ objects and then I choose to form pairs, amongst these 
 two subsets, I end up with fewer pairs than if I would consider the bigger set, so it is certainly smaller than $ n \choose 2$. 
I just don't see how it is smaller than $ {n-1\choose 2}$.
 A: We need to prove that
$$\frac{x(x-1)}{2}+\frac{(n-x)(n-x-1)}{2}\leq\frac{(n-1)(n-2)}{2}$$ or
$$x^2-x+n^2-(2x+1)n+x^2+x\leq n^2-3n+2$$ or
$$x^2-nx+n-1\leq0$$ or
$$(x-1)(x+1-n)\leq0,$$
which is true for $1\leq x\leq n-1.$
A: $$
f(x)=\binom{x}{2}+\binom{n-x}{2}=\frac{x(x-1)}{2}+\frac{(n-x)(n-x-1)}{2}=\frac{x(x-1)+(n-x)(n-x-1)}{2}=ax^2+bx+c
$$
for some $a, b, c\in\mathbb R$ with $a>0$. Because $a>0$ (a convex parabola) its maximum must lie on the boundary of the set $\{x:x\geq 1$ or $n-x\geq 1\}$, that is $x=1$ or $n-x=1\Leftrightarrow x=n-1$.
Finally we have
$$
f(x)\leq f(1)=f(n-1)=\binom{n-1}{2}
$$
A: Consider two complete graphs $K_x$ and $K_{n-x}$ and without loss of generality assume $x \le n-x$.
Now suppose we merge the vertices into a larger complete graph $K_{n-1}$, adding all remaining edges between the two previously disjoint graphs, but removing one of the vertices as a "tax". The question amounts to showing that the resulting graph has at least as many edges as the two smaller graphs together.
Removing a vertex from $K_x$ destroys $x-1$ edges. On the other hand, each of the remaining $x-1$ vertices can be matched with a vertex in $K_{n-x}$ since $x-1 < n-x$, so when the two graphs are merged, the number of edges created is at least the number destroyed, with equality when $x=1$.
A: Your method of splitting items in two groups actually gives an equality:
$$
\binom{n}{2}=\binom{x}{2}+\binom{n-x}{2}+x(n-x)
$$
(we can either choose both items from the first group, or both from the second, or one from each).
Now,
\begin{align}
\binom{n-1}{2}&=\binom{n}{2}-(n-1)\\
&=\binom{x}{2}+\binom{n-x}{2}+x(n-x)-(n-1)
\end{align}
and so your problem reduces to showing that $f(x)=x(n-x)-n+1$ is nonnegative for $1 \leq x \leq n-1$. For a fixed $n$, $f$ is quadratic in $x$ with roots $1$ and $n-1$; since the leading coefficient is negative, $f$ must be positive between the roots.
A: \begin{align}
{x\choose2} +{n-x\choose2} 
 &=\frac{(x-1)x}2 +\frac{(n-x)(n-x-1)}2 \\
 &=\tfrac12 (x^2-x +n^2-nx-n -nx+x^2+x) \\
 &=\tfrac12 (2x^2 -2nx+n^2-n) \\
 &=\tfrac12 (2x(x-n) +n(n-1))
\end{align}
Given $1 \leq x \leq n-1$ (and $x-n \leq -1$), then
\begin{align}
 &\leq \tfrac12 (2(n-1)(-1) +n(n-1)) \\
 &=\frac{(n-1)(n-2)}2 \color{blue}{\cdot \frac{(n-3)!}{(n-3)!}} \\
 &=\frac{(n-1)!}{2!(n-3)!} \\
 &={n-1\choose2}.
\end{align}
A: Writing them out,
${x\choose 2}+{n-x\choose 2} \leq {n-1\choose 2}$
becomes
$x(x-1)+(n-x)(n-x-1) \le (n-1)(n-2)
$
or
$x^2-x+n^2-n(x+x+1)+x^2-x
\le n^2-3n+2
$
or
$2x^2-2x
\le n(2x+1-3)+2
$
or
$2x^2-2x
\le n(2x-2)+2
$
or
$x^2-x
\le n(x-1)+1
$
or
$x(x-1)
\le n(x-1)+1
$
or
$(x-n)(x-1)
\le 1
$
which is true for
$x \ge 1$
and
$x \le n-1$.
This is false for $x=0$
or
$x=n$
where this algebra does not work.
