Tree Representation

At the most basic level, we represent trees as an adjacency matrix, a tree with $n$ vertices indexing these vertices as $0,1,2,\ldots,n-2,n-1$. A disadvantage to this approach is that trees which are isomorphic may not have the same adjacency matrix due to the ordering of vertices. For instance, a line on 3 vertices can appear as both of the following:

$$\left[ \begin{array}{ccc} 0 & 1 & 1\\ 1 & 0 & 0\\ 1 & 0 & ... ...ay}{ccc} 0 & 1 & 0\\ 1 & 0 & 1\\ 0 & 1 & 0\end{array}\right]$$

Nonetheless, we use this representation internally and address this issue later.

Consistent with usual convention, we will use $V(G)$ to denote the set of vertices in $G$, and $E(G)$ the set of edges in $G$.