A Characterization of the Indecomposable and Infinite Graphs

Let G = (V, A) be a directed graph. With each subset X of V is associated the directed subgraph G(X) = (X, A ∩ (X × X)) of G induced by X. In another respect, a subset X of V is an interval of G provided that for a, b ∈ X and x ∈ V − X, (a, x) ∈ A if and only if (b, x) ∈ A, and similarly for (x, a) and (x, b). For example, ∅, V and {x}, where x ∈ V, are intervals of G, called trivial intervals. A directed graph is indecomposable if all its intervals are trivial. The following characterization is proved. Given an infinite directed graph G = (V, A), G is indecomposable if and only if for every finite subset F of V, there is a finite subset F′ of V such that F ⊆ F′ and G(F′) is indecomposable.