Why the Center Reduces the Isomorphism Test
Rooted-tree isomorphism has a recursive description: compare the root branches, then compare the rooted trees hanging from those branches. For an unrooted tree there is no distinguished starting vertex. The center supplies a natural choice that every isomorphism must preserve. If the center is one vertex, root there. If it is two adjacent vertices, cut their edge and compare the two resulting rooted trees as an unordered pair.
All trees in this tutorial are finite, simple, and nonempty. An isomorphism \(f:V(G)\to V(H)\) is a bijection such that, for every \(u,v\in V(G)\), \(uv\in E(G)\) if and only if \(f(u)f(v)\in E(H)\). A rooted-tree isomorphism is an isomorphism that also maps the root of one tree to the root of the other. The two directions in the adjacency condition matter: an isomorphism preserves both edges and nonedges.
We use the rooted canonical code from the earlier material on canonical forms. For a rooted tree, regard each neighbor farther from the root as a child. Define the code recursively by \(C(v)=\langle C(w):w\text{ is a child of }v\rangle\), with the child codes sorted into a fixed order. The leaves have code \(L=\langle\rangle\). Thus the code records the multiset of child codes, not an ordering of the children.
This tutorial uses that criterion to compare the parts of an unrooted tree selected by its center. For a two-vertex center, remove the edge joining the centers, root each of the two components at the endpoint it contains, and keep the two codes unordered.
The Center-Based Test
Proof. An isomorphism maps paths to paths, and its inverse also maps paths to paths. Therefore it preserves distances: for every \(u,v\), \(d(u,v)=d(f(u),f(v))\). It follows that it preserves eccentricities and maps the center of \(T\) onto the center of \(T'\). In particular, the two trees must have the same number of center vertices.
If each has one center, any isomorphism maps center to center, so it is a rooted isomorphism between the trees rooted at their centers. The rooted-code criterion gives equality of the center codes. Conversely, if the center codes agree, the rooted-code criterion supplies a rooted isomorphism, which is also an isomorphism of the unrooted trees.
Suppose instead that each has two centers. The centers are adjacent, and their joining edge is mapped to the joining edge in the other tree. Deleting that edge leaves two components in each tree. An isomorphism maps the two rooted components onto the two rooted components in some order, so the unordered pairs of codes agree. Conversely, if the unordered pairs agree, pair the components with equal codes. The rooted-code criterion gives a rooted isomorphism on each paired pair of components. Combine these two bijections and map the central edge’s endpoints to the corresponding roots. The components are disjoint, and the only edge between them is the central edge, so the combined bijection preserves adjacency in both directions. It is an isomorphism of the original trees. \(\square\)
The proof gives a direct procedure: find each tree’s center; in the one-center case compute the root code, and in the two-center case delete the central edge and compute the two rooted codes. Compare the codes, sorting the two-component pair in the two-center case. The center theorem ensures these cases cover every nonempty tree.
Use distances or a center-finding method to determine whether there is one center vertex or two adjacent center vertices.
Root at the single center, or delete the central edge and root each component at its center endpoint.
Compare the single rooted codes, or sort and compare the two rooted codes. Equality is equivalent to isomorphism by the theorem.
Worked Comparisons
Worked Example: Isomorphic Trees with One Center
Let \(T\) have vertex set \(\{c,a,x,b,y,z\}\) and edge set \(\{ca,ax,cb,by,cz\}\). Let \(T'\) have vertex set \(\{r,p,q,s,t,u\}\) and edge set \(\{rp,pq,rs,st,ru\}\). Determine whether they are isomorphic using their centers.
In \(T\), the longest paths run between \(x\) and \(y\), or between \(x\) and \(z\), or between \(y\) and \(z\). Their lengths are \(4,3,3\), respectively; in particular, a diameter is \(x-a-c-b-y\), of length \(4\). The middle vertex of this diameter is \(c\), and the center is the single vertex \(c\). The same distance pattern holds in \(T'\), where \(r\) is the single center.
Compute the code outward from each center. Every leaf has code \(L=\langle\rangle\). The vertices \(a,b\) each have one child that is a leaf, so \(C(a)=C(b)=\langle L\rangle\). The same calculation gives \(C(p)=C(s)=\langle L\rangle\). At the roots, the child codes are therefore:
The codes are equal, so the trees are isomorphic. One explicit isomorphism is \(c\mapsto r\), \(a\mapsto p\), \(x\mapsto q\), \(b\mapsto s\), \(y\mapsto t\), and \(z\mapsto u\). It sends the five listed edges of \(T\) to the five listed edges of \(T'\), and the inverse sends those edges back.
Check: both trees have six vertices and degree multiset \(\{3,2,2,1,1,1\}\). The explicit bijection preserves all listed edges; because the two edge sets each have five edges and the map is bijective, it also preserves nonedges.
Worked Example: Isomorphic Trees with Two Centers
Let \(T\) have vertex set \(\{a,u,b,c,v,d,e\}\) and edge set \(\{au,ub,bc,uv,vd,ve\}\). Let \(T'\) have vertex set \(\{1,2,3,4,5,6,7\}\) and edge set \(\{41,42,45,56,63,57\}\). Compare them by their centers.
In \(T\), the path \(c-b-u-v-d\) has length \(4\), and its middle edge is \(uv\). The two sides of this edge have heights \(2\) from \(u\) and \(1\) from \(v\); their greatest cross-side distance is \(2+1+1=4\), so \(uv\) is the central edge. In \(T'\), the path \(3-6-5-4-1\) has length \(4\), with middle edge \(5-4\). The two rooted sides again have heights \(2\) and \(1\), so \(45\) is its central edge.
Delete \(uv\) in \(T\). Root the component containing \(u\) at \(u\): its children are the leaf \(a\), with code \(L\), and \(b\), whose child \(c\) is a leaf, so \(C(b)=\langle L\rangle\). This side has code \(\langle L,\langle L\rangle\rangle\). The component rooted at \(v\) has leaf children \(d,e\), giving code \(\langle L,L\rangle\). Thus the unordered pair is \(\{\langle L,\langle L\rangle\rangle,\langle L,L\rangle\}\).
Delete \(45\) in \(T'\). At root \(4\), the two children \(1,2\) are leaves, giving \(\langle L,L\rangle\). At root \(5\), one child \(7\) is a leaf and the other child \(6\) has leaf child \(3\); this gives \(\langle L,\langle L\rangle\rangle\). The unordered pair is the same, so the trees are isomorphic.
Check: the map \(u\mapsto5\), \(v\mapsto4\), \(a\mapsto7\), \(b\mapsto6\), \(c\mapsto3\), \(d\mapsto1\), and \(e\mapsto2\) sends the six edges of \(T\) to \(57,56,63,45,41,42\), exactly the edge set of \(T'\).
Worked Example: Equal Order but Nonisomorphic Two-Center Trees
Let \(A\) have vertex set \(\{u,a,b,c,v,d,e\}\) and edge set \(\{ua,ub,bc,uv,vd,ve\}\). Let \(B\) have vertex set \(\{r,a_1,a_2,a_3,s,b_1,b_2\}\) and edge set \(\{ra_1,ra_2,ra_3,rs,sb_1,sb_2\}\). Decide whether \(A\) and \(B\) are isomorphic.
Both trees have seven vertices. In \(A\), a longest path is \(c-b-u-v-d\), of length \(4\), so the center is the edge \(uv\). Deleting \(uv\) gives rooted codes \(\langle L,\langle L\rangle\rangle\) at \(u\) and \(\langle L,L\rangle\) at \(v\), as computed from their children. In \(B\), every path between a leaf at \(r\) and a leaf at \(s\) has length \(3\), so the center is \(rs\). Deleting \(rs\) gives codes \(\langle L,L,L\rangle\) at \(r\) and \(\langle L,L\rangle\) at \(s\).
The pairs differ because \(\langle L,\langle L\rangle\rangle\ne\langle L,L,L\rangle\). The theorem therefore shows that \(A\) and \(B\) are not isomorphic. The distinction is structural: one side of \(A\)'s center has a branch of length two, whereas all branches from either center of \(B\) are single edges.
Check: both edge sets contain six edges, and both trees have seven vertices. Thus order and size agree, but the rooted codes at the centers distinguish them.
Degenerate Case and Common Pitfalls
A tree with one vertex has that vertex as its unique center. Its rooted code is \(L=\langle\rangle\), so the procedure compares it correctly with another one-vertex tree. It cannot be isomorphic to a larger tree: an isomorphism is a bijection, and the vertex counts would differ.
Do not treat one-way adjacency preservation as isomorphism. For a concrete failure, let \(P_3\) have vertices \(\{x,y,z\}\) and edges \(\{xy,yz\}\), and let \(K_3\) have vertices \(\{a,b,c\}\) and edges \(\{ab,bc,ac\}\). The bijection \(x\mapsto a\), \(y\mapsto b\), \(z\mapsto c\) sends both edges of \(P_3\) to edges of \(K_3\). But \(xz\notin E(P_3)\), while \(ac\in E(K_3)\). The map is not an isomorphism, because it does not preserve adjacency in both directions. The center-code test compares full rooted structure and therefore does not make this mistake.
In the two-center case, also keep the pair of side codes unordered. An isomorphism may swap the two endpoints of the central edge, as in the second example. Requiring the code at one chosen endpoint to match the code at a preselected endpoint in the other tree would incorrectly reject such an isomorphism.
The method matters because it turns an unrooted comparison into the rooted comparison already encoded by recursive canonical forms. Centers are intrinsic: they are determined by distances, which is why an isomorphism cannot move them to a different structural role. The resulting test is exact, not just a necessary check: matching center descriptions constructs an isomorphism, while different descriptions rule one out.
Check Your Understanding
Use the center-based criterion and the rooted-code recursion to answer these questions.
- Why must an isomorphism preserve the number of center vertices?
- A tree has two centers joined by an edge. What rooted objects should be compared after removing that edge?
- Why is the pair of codes in the two-center case unordered?
- Explain why a bijection that sends every edge to an edge is not necessarily an isomorphism.
- What is the center code of a one-vertex tree, and why can it only be isomorphic to another one-vertex tree?