3.2. Trees and labelling
Among the connected graphs, the simplest yet most important are the trees. A tree is an acyclic connected graph, a forest is an acyclic graph.
Elementary properties of a tree:
- every edge of a tree T is a bridge.
- every block of a tree T is acyclic.
- the number of blocks to which a vertex v
belongs equals
.
- if then
is a forest with
components.
- every vertex of T that is not an end-vertex belongs to at least two blocks and is ecessarily a cut-vertex.
Theorem 3.6. Every nontrivial tree has at least two vertices of degree 1 (end-vertices).
Proof. Let be the degree sequence of a tree T of
order
. Since T is connected, so
.
If T had at most one vertex of degree 1, by the "Handshaking Lemma", we would have
and this is contradiction.
Theorem 3.7. A graph is a tree iff G is acyclic and
.
Proof.
-
Suppose that G is a tree. Then G is acyclic.
We show that
by induction on n. For
, the result is trivial.
Assume that the equality
holds for all trees with
vertices and m edges. Let T be a tree with
vertices and let v be an end-vertex of T.
The graph
is a tree of order n and so - by the induction hypotesis - the size of T' is
.
Since T has one more edge than T', it follows that T has
edges. Since
, the desired result follows.
-
Conversely, let
be an acyclic graph, where
. We need only verify that G is connected.
Denote by
the components of G, where
![]()
. Since each Gi is a tree, so
. Hence,
so that k = 1 and therefore G is connected.