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

\title{MH1301 Bonus Question 4}

\begin{document}
\maketitle

\noindent
The claim is false.

\noindent
First, consider the complete graph $G$ with $n$ vertices.
This means that:
\[
	diam(G) = apd(G) = 1
.\]
Then, if we were to append a string of $c$ vertices onto the graph $G$, we find that now:
\[
	diam(G) = c+1
.\]
And to find $apd(G)$ we must first find:
\[
	\sum_{u,v\in V}^{} d(u,v)
.\]
We can break this task into three parts, in the first part, we add up all the distances in the complete graph with $n$ vertices.
Since the distance between each pair of vertices in a complete graph is 1, the sum of the distances is the number of edges.
We know that the number of edges in a complete graph with $n$ vertices is:
\[
	\frac{n(n-1)}{2}
.\]
For the second part, we find the sum of the distances of the string of $c$ vertices.
In this case, we can count the number and associate:
\begin{align*}
	c=1 \implies & 0\\
	c=2 \implies & 1\\
	c=3 \implies & 2(1) + 1(2) = 4\\
	c=4 \implies & 3(1) + 2(2) + 1(3) = 10\\
	c=5 \implies & 3(1) + 2(2) + 1(3) = 20
\end{align*}
Which is the sum of the triangle numbers:
\[
	\begin{matrix}
		1 & & & & &\\
		1 & 2& & & &\\
		1 & 2& 3& & &\\
		1 & 2& 3& 4& &\\
		1 & 2& 3& 4& 5&\\
		1 & 2& 3& 4& 5& 6\\
	\end{matrix}
\]
These are \textbf{tetrahedral} numbers and their general equation is:
\[
	\frac{c(c+1)(c+2)}{6}
.\]
Lastly, for the third part, we have the distances from the vertices in the complete graph that are not adjacent to the string of $c$ vertices.
There are $n-1$ of these such vertices and they each have increasing distances from the string of vertices beginning with 2:
\[
	(n-1)\sum_{i=2}^{c+1} i
.\]
Evaluating the summation term we have:
\begin{align*}
	\sum_{i=2}^{c+1} i & = \frac{(c+1)(c+2)}{2} - \frac{2}{2}\\
			   & = \frac{c^2+3c+2}{2}-\frac{2}{2}\\
			   & = \frac{c^2+3c}{2}.
\end{align*}
So, putting all these terms together to calculate the value of $apd(G)$, we have:
\begin{align*}
	apd(G) & = \frac{\frac{n(n-1)}{2} + \frac{c(c+1)(c+2)}{6} + \frac{(n-1)(c^2+3c)}{2} }{C(n+c,2)}\\
	       & = \frac{\frac{n(n-1)}{2} + \frac{c(c+1)(c+2)}{6} + \frac{(n-1)(c^2+3c)}{2} }{\frac{(n+c)(n+c-1)}{2}}\\
	       & = \frac{n(n-1) + \frac{c(c+1)(c+2)}{3} + (n-1)(c^2+3c)}{(n+c)(n+c-1)}\\
	       & = \frac{n^2 + n(c^2+3c-1) +(\frac{2}{3}-2c-\frac{2}{3}c^2)}{n^2 + n(2c-1) + (c^2-c)}.
\end{align*}
Evaluating the limit of the expression we have:
\begin{align*}
	\lim_{n \to \infty} apd(G) & = \lim_{n \to \infty}\frac{n^2 + n(c^2+3c-1) +(\frac{2}{3}-2c-\frac{2}{3}c^2)}{n^2 + n(2c-1) + (c^2-c)}\\
	\intertext{Dividing top and bottom by highest power of $n$:}
				   & = \lim_{n \to \infty}\frac{1 + \frac{c^2+3c-1}{n} + \frac{\frac{2}{3}-2c-\frac{2}{3}c^2}{n^2}}{1 + \frac{2c-1}{n} + \frac{c^2-c}{n^2}}\\
				   & = 1.
\end{align*}
So, finally we have:
\[
	\lim_{n \to \infty}\frac{diam(G)}{apd(G)} = \frac{c+1}{1} > c
.\]
Which contradicts the claim.
\end{document}
