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.