Augmentation

Another utility that is necessary is augmentation. As we deal exclusively with trees, and not general graphs, it must be the case that any two vertices in a tree are have some path between them. The only way to introduce a vertex to the tree then is also add and edge from it to some existing vertex in the tree. We denote a tree formed by adding a new vertex and edge incident to a existing vertex $v$ in tree $T$ as $\mathit{Augment}(v,T)$. Then, as an example, consider $\mathit{Line}(3)$ and $\mathit{Augment}(1,Line(3))$.

$$\mathit{Line}(3) = \left[ \begin{array}{ccc} 0 & 1 & 0 \\ ... ...& 1 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{array}\right]$$