When Do Two Trees Have the Same Structure?
Two trees can look different because their vertices have different names or because they are drawn in different ways, while still having exactly the same adjacency structure. Tree isomorphism formalizes the idea that only the structure matters: vertex names and the way a tree is drawn can change, but which pairs of vertices are adjacent must be preserved. In a rooted tree, there is one additional requirement: the distinguished root must map to the distinguished root.
All graphs in this tutorial are finite and simple. A tree is a connected graph with no cycles. A graph isomorphism is a bijection between vertex sets that preserves adjacency in both directions. A rooted tree is a tree together with a specified vertex called its root. Distances in a tree are measured by the number of edges in the unique path between the vertices.
Thus an isomorphism of unrooted trees has no designated vertex it must send to a specified target. A rooted isomorphism has the same adjacency requirement, but must also carry the root to the other root. Every rooted isomorphism gives an isomorphism of the underlying unrooted trees, but the converse need not hold for the chosen roots.
Structural Features an Isomorphism Preserves
A property that has the same value in isomorphic graphs is called an isomorphism invariant. Degrees are basic invariants: the neighbors of a vertex must correspond bijectively to the neighbors of its image. Distances are also preserved. For disconnected graphs, we use the convention that the distance between vertices in different connected components is \(\infty\); this lets the distance statement cover all pairs.
Proof. Fix a vertex \(v\). Because \(f\) preserves adjacency, each neighbor of \(v\) maps to a neighbor of \(f(v)\). Because \(f\) is a bijection and its inverse also preserves adjacency, every neighbor of \(f(v)\) is the image of exactly one neighbor of \(v\). Thus the two neighbor sets have equal size, so \(\deg_G(v)=\deg_H(f(v))\).
Now fix \(u,v\). If \(u\) and \(v\) are connected, a shortest \(u\)-\(v\) path of length \(k\) maps to an \(f(u)\)-\(f(v)\) path of length \(k\), so \(d_H(f(u),f(v))\le k=d_G(u,v)\). Applying the same argument to the inverse isomorphism gives \(d_G(u,v)\le d_H(f(u),f(v))\). Hence the distances are equal. If \(u\) and \(v\) are disconnected, an \(f(u)\)-\(f(v)\) path would map back under \(f^{-1}\) to a \(u\)-\(v\) path, which is impossible. So their images are disconnected too, and both distances are \(\infty\). \(\square\)
In a rooted tree, the distance from the root gives each vertex its depth. The vertices at depth \(i\) form level \(i\). Every nonroot vertex has a parent: the vertex immediately before it on the unique path from the root. Its children are the adjacent vertices one step farther from the root.
Proof. Let \(f:(T,r)\to(U,s)\) be a rooted isomorphism. It maps \(r\) to \(s\), and the distance-preservation theorem gives \(d_T(r,v)=d_U(s,f(v))\) for every \(v\). Therefore \(v\) and \(f(v)\) have the same depth, and each level maps to the corresponding level. If \(x\) is the parent of \(v\), then \(xv\) is an edge and \(x\) is one step closer to \(r\) than \(v\). Its image \(f(x)\) is adjacent to \(f(v)\) and one step closer to \(s\), so \(f(x)\) is the parent of \(f(v)\). Reversing the argument shows that children correspond as well. \(\square\)
These facts provide quick tests. Different degree multisets rule out isomorphism; for rooted trees, different numbers of vertices at any level rule out rooted isomorphism. Passing such tests does not by itself prove that an isomorphism exists.
Worked Example: Verifying a Rooted Isomorphism
Let \(R\) have vertex set \(\{r,a,b,c,d,e\}\), edge set \(\{ra,rb,ac,ad,be\}\), and root \(r\). Let \(S\) have vertex set \(\{s,x,y,u,v,w\}\), edge set \(\{sx,sy,xu,xv,yw\}\), and root \(s\). Define \(f\) by \(r\mapsto s\), \(a\mapsto x\), \(b\mapsto y\), \(c\mapsto u\), \(d\mapsto v\), and \(e\mapsto w\).
The six images are distinct and exhaust \(V(S)\), so \(f\) is a bijection. The edges of \(R\) map as follows: \(ra\mapsto sx\), \(rb\mapsto sy\), \(ac\mapsto xu\), \(ad\mapsto xv\), and \(be\mapsto yw\). These are exactly the five edges of \(S\). Since the map is a bijection and the edge sets correspond exactly, adjacency is preserved in both directions. Finally, \(f(r)=s\), so this is a rooted isomorphism.
Check: The degrees in \(R\) are \(\deg(r)=2\), \(\deg(a)=3\), \(\deg(b)=2\), and \(\deg(c)=\deg(d)=\deg(e)=1\). In \(S\), \(\deg(s)=2\), \(\deg(x)=3\), \(\deg(y)=2\), and \(\deg(u)=\deg(v)=\deg(w)=1\). The map matches these degrees vertex by vertex. The level sizes from each root are \(1,2,3\): in \(R\), the levels are \(\{r\},\{a,b\},\{c,d,e\}\); in \(S\), they are \(\{s\},\{x,y\},\{u,v,w\}\).
Unrooted Isomorphism Does Not Have to Preserve Chosen Roots
Worked Example: The Same Tree with Different Roots
Let \(G\) have vertex set \(\{c,a,b,d\}\) and edge set \(\{ca,cb,cd\}\). Compare the rooted trees \((G,c)\) and \((G,a)\).
As unrooted trees, they are isomorphic: the identity map on \(V(G)\) preserves every edge. But it does not map the first root \(c\) to the second root \(a\). In fact, no rooted isomorphism can do so. The root \(c\) has degree \(3\), while the target root \(a\) has degree \(1\). Since an isomorphism preserves degrees, any isomorphism sending \(c\) to \(a\) is impossible.
Check: The degree multiset of \(G\) is \(\{3,1,1,1\}\), regardless of the chosen root. Unrooted isomorphism holds, but the root degrees \(3\) and \(1\) do not match, ruling out rooted isomorphism for these choices.
This distinction matters whenever the root represents a meaningful starting point, such as a source, a designated ancestor, or the top of a rooted hierarchy. If the root is merely an auxiliary choice and is not part of the structure being compared, the relevant question is unrooted isomorphism instead.
Degree Data Can Rule Out Isomorphism, but Cannot Prove It
The multiset of vertex degrees is an easy-to-compute invariant. It is often useful as an initial test, but it records only how many neighbors each vertex has; it does not record how those neighbors are connected to one another or how branches are arranged. Distances between leaves can expose some of this missing structure in trees.
Worked Example: Equal Degree Multisets, Different Branching
Let \(T\) have vertex set \(\{o,a,b,x,y,z,w\}\) and edge set \(\{oa,ob,ax,ay,bz,zw\}\), rooted at \(o\). Let \(U\) have vertex set \(\{p,q,r,t,s,u,v\}\) and edge set \(\{pq,pr,pt,qs,ru,uv\}\), rooted at \(p\). Each graph is connected and has seven vertices and six edges; the displayed branches have no cycles, so both are trees.
From root \(o\), the levels of \(T\) are \(\{o\},\{a,b\},\{x,y,z\},\{w\}\), with sizes \(1,2,3,1\). From root \(p\), the levels of \(U\) are \(\{p\},\{q,r,t\},\{s,u\},\{v\}\), with sizes \(1,3,2,1\). Thus the rooted trees are not rooted-isomorphic: their roots have different degrees, and their level sizes also differ.
For the unrooted comparison, compute the degree multiset of each tree. In \(T\), \(a\) has degree \(3\); \(o,b,z\) have degree \(2\); and \(x,y,w\) have degree \(1\). In \(U\), \(p\) has degree \(3\); \(q,r,u\) have degree \(2\); and \(s,t,v\) have degree \(1\). Both degree multisets are therefore \(\{3,2,2,2,1,1,1\}\), so this test does not decide the unrooted question.
Now compare distances between leaves. The leaves of \(T\) are \(x,y,w\). Their pairwise distances are \(d_T(x,y)=2\), using \(x-a-y\); \(d_T(x,w)=5\), using \(x-a-o-b-z-w\); and \(d_T(y,w)=5\), using \(y-a-o-b-z-w\). Thus the multiset of leaf-pair distances is \(\{2,5,5\}\).
The leaves of \(U\) are \(s,t,v\). Their pairwise distances are \(d_U(s,t)=3\), using \(s-q-p-t\); \(d_U(s,v)=5\), using \(s-q-p-r-u-v\); and \(d_U(t,v)=4\), using \(t-p-r-u-v\). Thus the multiset is \(\{3,4,5\}\). These multisets differ, so the trees are not isomorphic: an isomorphism must map degree-one vertices to degree-one vertices and preserve every distance between their images.
Check: The two trees have the same order, size and degree multiset, but their leaf-pair distance multisets are different. The distance calculation rules out unrooted isomorphism, as well as rooted isomorphism.
A Practical Test for a Candidate Map
When a proposed map is given, verify the definition rather than relying only on visual similarity. Check that the map is a bijection, that every edge maps to an edge, and that nonedges map to nonedges. Equivalently, after applying the bijection, the image of the entire edge set must equal the target edge set. For rooted trees, also check that the root maps to the root.
When no map is proposed, compare invariants to search for contradictions. Degrees, distances, and—in the rooted setting—depths and level sizes are useful necessary conditions. If any such values disagree, the trees cannot be isomorphic in the relevant sense. If they agree, the test is inconclusive: the trees may still have different branching arrangements.
Common Pitfall
A common mistake is to conclude that two trees are isomorphic as soon as their degree multisets agree. In the example above, one might write, “Both degree multisets are \(\{3,2,2,2,1,1,1\}\), so the trees are isomorphic.” The conclusion does not follow: the degree multiset is only a necessary condition. Here the leaf-pair distance multisets are \(\{2,5,5\}\) for \(T\) and \(\{3,4,5\}\) for \(U\), and that difference proves the trees are not isomorphic.
A related error is to treat rooted and unrooted isomorphism as interchangeable. The identity map in the star example establishes an unrooted isomorphism, but it does not preserve the chosen roots, and the root degrees show that no root-preserving map exists. Always identify whether the roots are part of the structure being compared.
Check Your Understanding
Use the definitions and invariants from this tutorial to answer the following questions.
- State the two conditions a bijection must satisfy to be an isomorphism of rooted trees.
- Why does an isomorphism preserve distances even when the graph may be disconnected?
- Can rooted trees with different level sizes be rooted-isomorphic? Justify your answer.
- Two trees have the same degree multiset. What can you conclude, and what can you not conclude?
- For the trees \(T\) and \(U\) in the example, list their leaf-pair distance multisets and explain how these rule out unrooted isomorphism.