Adjacency

Perhaps the most trivial operation that can be performed on an adjacency matrix is to make two vertices adjacent to each other. Of course, performing this operation on a tree would create cycles if the vertices were not already adjacent, so this operation is defined on graphs, not only trees. To make any vertices $u$ and $v$ adjacent in the graph, we set the coordinates $(u,v)$ and $(v,u)$ in the adjacency matrix to 1. An analogous operation operation holds for making vertices non-adjacent. As we deal solely with simple graphs, it is an error to try to make a vertex $v$ adjacent with itself. We denote this operation $\mathit{MakeAdjacent}(u,v,G)$.

$$\mathit{MakeAdjacent}\left(0,1, \left[ \begin{array}{cc} 0 ... ...\left[ \begin{array}{cc} 0 & 1\\ 1 & 0 \end{array} \right]$$