A forest is a graph that contains no cycles, and a connected forest is a tree. For example, Fig. 1.1 shows a forest with four components, each of which is a tree

". Note that trees and forests are simple graphs.

                                                               Fig. 1.1

Another definition

A forest is an acyclic graph. The connected components of a forest are therefore trees, which explains the use (very natural!) of the terminology.

Forests generalize trees.

Proposition 1.1. In a forest G, we have m ≤ n − 1, with equality if and only if G is a tree.

Proof. Given C₁, C₂, ..., C_p the connected components of G, apply proposition( If G is a tree then m = n − 1.) to each of these components, denoting respectively n_i and

m_i the number of vertices and the number of edges of C_i. By adding all these equalities, for i =1, 2,...,p, we then have:

Thus:

                                m = n − p

and since p ≥ 1(p is the number of connected components of G):

                               m ≤ n − 1

Equality occurs if and only if p = 1, that is if and only if G is connected. Since G is by hypothesis acyclic, this means if and only if G is a tree.

Graph Theory  and Applications ,Jean-Claude Fournier, WILEY, page(47)

Introduction to  Graph Theory  ,Fourth edition,  Robin J. Wilson, 1998

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength