labeled by the vertices in $V$ and whose entries hold edge weights. Thus, the adjacency matrix is an $n\times n$ matrix where $|V|=n$. The adjacency matrix $A_G$ (or simply $A$ for shorthand) for a graph $G$ is given by $$A_{ij} = \begin{cases}
0, &\text{if } i=j,\\
w_{ij} ,& \text{if } i\ne j.\\
\end{cases}$$ An important measure of local connectivity is given by the *valency* $v_i$ of a node $i$, with $v_i = {\sum\limits_{j=1}^{n}w_{ij}}$. For unweighted graphs, the valency of any node is simply the number of edges incident at that node, otherwise known as the *degree* of the node. We will also define the graph diameter, $\delta(G)$, as the maximization of the shortest distance between two nodes on the graph over all pairs of nodes.

Graphs may also be described by the *Laplacian*. The algebraic Laplacian $L$ is given by $$L_{ij} = \begin{cases}
v_i,&\text{if } i=j,\\
-w_{ij},& \text{if } i\ne j. \\
\end{cases}$$ The algebraic Laplacian is closely related to the adjacency matrix, since we may write $L = \Delta - A$, where $\Delta = \text{diag}{\left(v_1,\ldots,v_n\right)}$ is the diagonal matrix of vertex valencies. The eigenvalues of the algebraic Laplacian give us bounds on various graph properties, as discussed further in 