MATH 180 - GRAPH THEORY

LECTURE 10 – TREES

We completed the proof of Whitney’s theorem about 2-connected graphs which can be
found in the lecture notes for Lecture 9.
1. Trees
Definition 1.1. A tree is a connected graph with no cycles.
Trees can be characterized in many equivalent ways.
We begin with a lemma.
Definition 1.2. A vertex v is a leaf or end-vertex of a graph G if it has degree 1.
Lemma 1.3. (Leaf lemma) Every tree with ≥ 2 vertices contains at least two leaves.
Proof. Let P = (v0 , e1 , v1 , . . . , et , vt ) be a path of maximal length in G. Since G is connected
and G has ≥ 2 vertices, it has at least one edge. Therefore, the length of P is ≥ 1, so v0 ̸= vt .

Claim: v0 and vt are leaves.

If v0 is not a leaf, then there are ≥ 2 edges incident to v0 . Therefore, there is an edge
e = {v0 , v} different from {v0 , v1 } incident to v0 . If v is already a vertex in the path, then P
along with e forms a cycle, contradicting that G is a tree. If v is not a vertex in P , then we
can increase the length of P by adding e, contradicting maximality of P . □
Lemma 1.4. (Tree-growing lemma) Let G be a graph and v a leaf of G. The following are
equivalent.
(1) G is a tree.
(2) G − v is a tree.
Proof. =⇒: Suppose G is a tree. Suppose x, y are vertices of G − v. Since G is connected,
there is a path in G from x to y. This path cannot have a vertex of degree 1 aside from
x, y, so v is not on it. Therefore, the path is contained in G − v. Hence, G − v is connected.
Any cycle in G−v would also be a cycle in G, so G−v has no cycles. Therefore, G−v is a tree.

⇐=: Suppose G − v is a tree. Since any cycle contains only vertices of degree ≥ 2, a
cycle in G would also be a cycle in G − v. Therefore, G has no cycles. Let u be the vertex
incident to v in G. Since G − v is connected, u is connected to every vertex of G − v by a
path. Moreover, u is connected to v by the edge {u, v}, so every vertex is connected to u in
G. Therefore, G is connected. □

1
 MATH 180 - GRAPH THEORY
LECTURE 11 – CHARACTERIZATION OF TREES

1. Basic facts about trees

In Lecture 10, we proved the following two lemmas.
Lemma 1.1. (Leaf lemma) Every tree with ≥ 2 vertices contains at least two leaves.
Lemma 1.2. (Tree-growing lemma) Let G be a graph and v a leaf of G. The following are
equivalent.
(1) G is a tree.
(2) G − v is a tree.
Lemma 1.3. If G = (V, E) is a tree, then |V | − |E| = 1.
Proof. We argue by induction on the number of vertices |V |. If |V | = 1, then G is a single
vertex and this is true. For the induction step, by the tree-growing lemma, removing a leaf
v yields a tree G − v with one fewer vertex and one fewer edge. □

2. Euler characteristic
The number of connected components in G is called the zeroth Betti number of G, and
is denoted by b0 = b0 (G). The first Betti number of a graph G, denoted b1 = b1 (G), is the
maximal number of edges in G whose removal does not change the number of connected
components. (We keep all the vertices.) Note that it is not clear that this is well-defined
independent of the order in which we removed edges. We will prove this soon. For example,
b0 (K4 ) = 1 and b1 (K4 ) = 3. Intuitively, b1 (G) is the number of independent cycles in G.
Lemma 2.1. A graph G = (V, E) is a forest if and only if b1 = 0. Then b0 = |V | − |E| and
b1 = 0.
Proof. Suppose G is a forest. If b1 ̸= 0, then there is an edge e = {u, v} which can be
removed without increasing b0 . Let Gi denote the component containing e. Then Gi − e is
connected, so there is a path P between u and v in Gi − e. Then P along with e forms a
cycle in G, a contradiction.
Suppose b1 = 0 and suppose G is not a forest. Then there is a cycle C in G. Let e = {u, v}
be an edge in C. If we remove e, then we do not change the connected components of G. To
show this, suppose x, y ∈ V are in the same connected component of G. so there is a path
Q between x to y in G. Then we have the following two cases:
(1) Q does not contain e: Then Q is also a path between x and y in G − e.
(2) Q contains e: We replace e in Q by P to get a walk from x to y in G − e.
Therefore the connected components do not change upon removing e, so b1 ≥ 1, a contra-
diction.
1
2 MATH 180 - GRAPH THEORY LECTURE 11 – CHARACTERIZATION OF TREES

Let Gi = (Vi , Ei ), i = 1, . . . , b0 , denote the subtrees of G. By Lemma 1.3, |Vi | − |Ei | = 1,

so that
Xb0
|V | − |E| = (|Vi | − |Ei |) = b0 .
i=1
□
Theorem 2.2. For any graph G = (V, E), we have
|V | − |E| = b0 − b1 .
This number χ(G) is called the Euler characteristic of G.
Proof. Repeat the operation “remove an edge contained in a cycle” until we are left with a
forest. Both |V | and b0 do not change during this process. Therefore, this forest has |V | − b0
edges. It follows that we removed |E| − |V | + b0 edges, so b1 = |E| − |V | + b0 . □
This proof shows that the number of edges removed during the process described above
does not depend on the choices made, so b1 is well-defined.
Corollary 2.3 (Characterization of trees). Any three of the following properties of a graph
G imply the fourth:
(1) G is connected;
(2) G is acyclic;
(3) G has n vertices;
(4) G has n − 1 edges.
Proof. These properties can be restated as follows:
connected b0 = 1
acyclic b1 = 0
has n vertices |V | = n
has n − 1 edges |E| = n − 1
Now use |V | − |E| = b0 − b1 . □
 MATH 180 - GRAPH THEORY
LECTURE 12 – ISOMORPHISMS OF TREES

1. Isomorphism of trees
The goal of this lecture is to classify trees. What does it mean to classify mathematical
objects? Let us look at some examples.
(1) Sets: Suppose we want to classify all finite sets. There is no meaningful answer that
we can give since there are lots of finite sets. However, the sets {1, 2, 3} and {a, b, c}
have the same set-theoretic properties and we do not want to distinguish them. In
other words, we do not care about the names of the objects. The precise way to say
this is we classify sets up to isomorphism i.e. up to bijections, so we view sets that
are in bijection as the same. Finite sets up to bijection are classified by cardinality.
(2) Finite dimensional vector spaces: Again there are lots of vector spaces but if we only
care about the vector space structure and not the names of the vectors, then we
consider vector spaces modulo isomorphisms which are in this case invertible linear
transformations. Then they are classified by dimension.
We have already seen that it is very hard to classify graphs upto isomorphism and the best
we could do was give upper and lower bounds. However it turns out that if we restrict to
trees, there is a nice answer.
We will first describe two new classes of trees which have recursive structures that make
it easy to find invariants.

Definition 1.1. A rooted tree is a pair (T, r) where T is a tree and r ∈ V (T ) is a vertex
called the root. There is a unique path from r to any other vertex. If x, y ∈ V (T ) and
{x, y} ∈ E(T ) is an edge on the path from r to y, then x is called the parent of y and y is
called a child of x.

Definition 1.2. An isomorphism of rooted trees (T, r) and (T ′ , r′ ) is a graph isomorphism

f : V (T ) → V (T ′ ) of the trees T and T ′ such that f (r) = r′ .

Definition 1.3. A planted tree is a tree (T, r) along with a drawing of T in the plane consid-
ered up to continuous deformations (more precisely, isotopy). By a continuous deformation,
we can assume that in this drawing, the root is marked with an arrow pointing down, and
the children of each vertex lie above that vertex. Equivalently, a planted tree is a triple
(T, r, ν), where ν is a collection of linear orderings (νv )v∈V (T ) , where νv is a linear ordering
of the children of v which says in what order the children are drawn from left to right.

Definition 1.4. An isomorphism of planted trees is an isomorphism of rooted trees that

preserves the orderings ν of the children.

Remark 1.5. Intuitively, isomorphic planted/rooted trees have the same structure but only
differ in the labeling of the vertices. Isomorphism classes are unlabeled planted/rooted trees.
1
2 MATH 180 - GRAPH THEORY LECTURE 12 – ISOMORPHISMS OF TREES

1.1. Code of a planted tree. We assign to each vertex of a planted tree P its code, a
string code(P ) over the alphabet {±1}, by the following rule. Imagine that there is a worm
that lives at the root of the tree. It crawls along the tree starting from the left of the root
and records a 1 if it is moving away from the root and −1 if it is moving towards the root.
The resulting string of ±1 is the code of the planted tree. We will write − instead of −1 for
clarity.

Which binary strings arise as codes of planted trees?

Proposition 1.6. Let P be a planted tree on n + 1 vertices. Then code(P ) has length 2n.
Suppose code(P ) = a1 · · · a2n . Then any initial sum is nonnegative, i.e., a1 +a2 +· · ·+ak ≥ 0
for all 0 ≤ k ≤ 2n.
Proof. Each edge is used twice by the worm, once going away from the root and once going
towards the root, so the number of letters in the code is 2|E| = 2(n + 1 − 1) = 2n. The
initial sum a1 + · · · + ak is the distance of the worm at time k from the root so it must be
nonnegative. □
Remark 1.7. Such a sequence of ±1’s is called a ballot sequence.
Since the code only depends on the structure of the plane tree, it is invariant under
isomorphisms.
Theorem 1.8. The function
code : {planted trees modulo isomorphism (unlabeled planted trees)} → {ballot sequences}.
is a bijection.
Proof. There is an inverse which can be described as follows. Consider the path from (0, 0)
to (2n, 0) using steps (1, 1) for every 1 and (1, −1) for every −1 in the ballot sequence.
 MATH 180 - GRAPH THEORY LECTURE 12 – ISOMORPHISMS OF TREES 3

Such a path is called a Dyck path. The ballot sequence condition says that this path never
goes below the x-axis. Glue together the steps that are across from each other to get the
planted tree (reflected across the horizontal line due to choice of conventions). □

Example 1.9. The bijection between unlabeled planted trees and ballot sequencse for n =
0, 1, 2, 3 is shown below:

Remark 1.10. The theorem implies that the number of unlabeled planted trees on n + 1
vertices is equal to the number of ballot sequences of length 2n. This number is called the nth
Catalan number and is one of the most important sequences of numbers in combinatorics.
There are more than two hundred objects counted by Catalan numbers; see Richard Stanley’s
book.

1.2. Code of a rooted tree. We embed the set of unlabeled rooted trees into the set of
unlabeled planted trees by choosing a canonical planting. We do this by looking at all possible
ways of planting the unlabeled rooted tree and choosing the lexicographically smallest one
(smallest in the dictionary order where −1 comes before 1).
The code of a rooted tree is the composition

code
{unlabeled rooted trees} → {unlabeled planted trees} −−→ {ballot sequences}.

We can compute it recursively as follows. Suppose R = (T, r) is a rooted tree. Let

R1 , . . . , Rm denote the children of r. Compute the plantings of R1 , . . . , Rm and the codes
code(R1 ), . . . , code(Rm ). Order R1 , . . . , Rm in lexicographic order of their codes to get a
planting of R.
4 MATH 180 - GRAPH THEORY LECTURE 12 – ISOMORPHISMS OF TREES

1.3. Code of a tree. We embed unlabeled trees into unlabeled rooted trees by making a
canonical choice for the root. We do this by choosing the root to be the “most central”
vertex in the tree.
For a vertex v of G, let exG (v) denote the maximum distance from v to a vertex of G,
called the excentricity of v. Let C(G) := {v ∈ V : exG (v) is minimum} denote the center of
G.
Proposition 1.11. For any tree T , C(T ) has at most two vertices. If C(T ) has two vertices
x, y, then {x, y} is an edge of T .
Proof. Let T = (V, E) be a tree. If T has ≤ 2 vertices, then its center is V . If not, it has at
least two leaves. Not all the vertices of T are leaves, so T ′ obtained from T by deleting all
the leaves is nonempty. Then,
exT ′ (v) = exT (v) − 1,
so C(T ) = C(T ). Keep doing this until T ′ has either one or two vertices.
′
□
If C(T ) is a single vertex v, define the code to be the code of (T, v). If C(T ) consists of
two vertices x, y, consider the two sub-trees Tx , Ty of T − {x, y}, where Tx contains x and Ty
contains y. Let A and B denote the codes of Tx , Ty respectively. Let x be the root if A ≤ B
in lexicographic order and let y be the root if B ≤ A in lexicographic order.
The code of a tree is the composition
code
{unlabeled trees} → {unlabeled rooted trees} → {unlabeled planted trees} −−→ {ballot sequences}.