\documentclass[a4paper]{report}
\input{preamble.tex}

\title{MH1301 Bonus Question 3}

\begin{document}
\maketitle

\noindent
1. First we show that the following equality holds:
\[
	n-k\leqslant m
\]
If we separate $G$ into its $k$ different sub-graphs, we have the graphs $G_1,G_2,\dotsc,G_k$ with $n_1,n_2,\dotsc,n_k$ vertices respectively.
We know that the minimum number of edges required to connect $n$ vertices is $n-1$.
Thus, the lower bound for the total number of edges in $G$ will have $k$ sub graphs, each with the minimum number of edges required.
\begin{note}
	$n_1+n_2+n_3+\dotsb+n_k=n$
\end{note}
Then if we add the number of edges in each minimised sub graph, we have:
\begin{align*}
	\sum_{i=1}^{k} (n_i-1) & = \sum_{i=1}^{k} n_i - \sum_{i=1}^{k} 1\\
			       & = (n_1 + n_2 +\dotsb+n_k) -k\\
			       & = n-k.
\end{align*}
Thus the minimum number of edges in $G$ is $n-k$, so we have:
\[
n-k\leqslant m
.\]

\bigbreak
\noindent
2. To show that the following equality holds:
\[
	m\leqslant \frac{(n-k)(n-k+1)}{2}
\]
Note that if we fix some arbitrary $n,k\in\mathbb{Z}$ and maximize the number of edges, we have a graph where there are $k-1$ sub graphs with only one vertex and one big sub-graph which is a complete graph.
\begin{proof}
	If we consider that instead, we have $k$ connected components, but of the $k$ connected components, 2 graphs have more than 1 vertex.
	Let us call these graphs $G_1,G_2$ which have $n_1,n_2$ vertices respectively, where both sub graphs are complete graphs.

	\bigbreak
	Then if we pick the graph with less vertices, which for this example we choose $G_2$, and take one of its vertices and remove it, we end up removing  $n_2-1$ edges.
	Then, if we add the removed vertex to $G_1$, we add $n_1$ edges.

	\bigbreak
	Since $n_2-1<n_1$ we have increased the total number of edges in the graph.
	Therefore the maximum number of edges is achieved when exactly one component has more than one vertex.
\end{proof}
The big sub-graph will have exactly $n-k+1$ vertices, since all the other components contain exactly one vertex.
Since this graph is a complete graph we can obtain its number of edges:
\[
	{n-k+1\choose 2} = \frac{(n-k)(n-k+1)}{2}
.\]
Which is the upper limit for the number of edges in a graph with $n$ vertices and $k$ connected components, and therefore:
\[
m\leqslant \frac{(n-k)(n-k+1)}{2}
.\]
Which ultimately means that:
\[
n-k\leqslant m \leqslant \frac{(n-k)(n-k+1)}{2}
.\]
As required.

\end{document}
