Proposition 1

Let G be a graph. Every forest of G is contained in a maximal forest of G; in particular, there exists a maximal forest of G.

In order that a forest of G be maximal, it is necessary and sufficient that the set of its vertices be equal to the set of vertices of G and that its connected components be those of G.

Let $A_0$ be a forest of G. The set of forests of G, endowed with the order relation “A is a subgraph of B”, is inductive. Consequently there exists a maximal forest of G of which $A_0$ is a subgraph (E, III, p. 21, Cor. 1).

The subgraph of G whose set of vertices is Som(G) and whose set of arrows is empty is a forest of G. There therefore exists a maximal forest of G.

Let A be a maximal forest of G. Let us prove that A and G have the same set of vertices. The subgraph of G whose set of vertices is Som(G) and whose set of arrows is Fl(A) is a forest and has A as a subgraph. Hence Som(A) = Som(G).

Let us now prove that A and G have the same connected components. Since an arrow of A is an arrow of G, every connected component of A is contained in a connected component of G. Since A and G have the same set of vertices, it is sufficient to prove that two vertices of G which are in the same connected component of G are in the same connected component of A. If this is not the case, the relation $R_A$, “being in the same connected component of A”, is strictly finer than the relation $R_G$, and there exist two vertices of G which are not in the same connected component of A but which are nevertheless joined by an arrow $f$ of G. Let B be the oriented subgraph of G whose set of vertices is Som(G) and whose set of arrows is Fl(A) $\cup \{f, f\}$; let us prove that B is a forest of G. Let $c= (a_0, f_1, . . . , f_n, a_n)$ be a non-constant loop without backtracking in B of minimal length. Since A is a forest, the loop $c$ is not a loop in A. Let $i$ (resp. $j$) be the smallest (resp. the largest) integer of $\{0, . . . , n\}$ such that $a_0$ and $a_i$ (resp. $a_j$ and $a_n$) are not in the same connected component of A. This means that the arrows $f_i$ and $f_{j+1}$ are oriented arrows of B associated with the edge $\{f, f\}$ and that they are opposite. Since the loop $c$ is without backtracking, $f_{i+1}=\not\overline{f_i}$, hence $i=\not j$ and the path $(a_i, f_{i+1}, a_{i+1}, . . . , f_j, a_j)$ is a non-constant loop without backtracking in B of length $< n$, contrary to the assumption that $c$ is of minimal length. It follows that B is a forest. This contradicts the assumption that A is a maximal forest of G.

Let now A be a forest of G such that Som(A) = Som(G) and $\pi_0(A) =\pi_0(G)$; let us prove that it is a maximal forest of G. It is enough to prove that, if $f\notin$ Fl(A), the subgraph B of G with set of vertices Som(G) and set of arrows Fl(A) $\cup \{f, f\}$ is not a forest. By hypothesis, the points $o(f)$ and $t(f)$ are in the same connected component of A; there therefore exists a path $c$ without backtracking in A joining $o(f)$ to $t(f)$. Then the path $c*\overline{f}$ is a nonconstant loop without backtracking in B, which shows that B is not an oriented forest.