There are many equivalent definitions of a forest Prove that

There are many equivalent definitions of a forest. Prove that the following conditions on a simple Graph G are equivalent.

a) Each component of G is tree.

b) G is acyclic.

Solution

A graph is a tree if and only if there is exactly one path between every pair of its vertices.

Let G be a graph and let there be exactly one path between every pair of vertices in G. So G is connected. Now G has no cycles, because if G contains a cycle, say between vertices u and v, then there are two distinct paths between u and v, which is a contradiction. Thus G is connected and is without cycles, therefore it is a tree. Conversely, let G be a tree. Since G is connected, there is at least one path between every pair of vertices in G. Let there be two distinct paths between two vertices u and v of G. The union of these two paths contains a cycle which contradicts the fact that G is a tree. Hence there is exactly one path between every pair of vertices of a tree.

A graph having no cycles is said to be acyclic. A forest is an acyclic graph.

A tree is a connected graph without any cycles, or a tree is a connected acyclic graph. The edges of a tree are called branches. It follows immediately from the definition that a tree has to be a simple graph (because self-loops and parallel edges both form cycles).