= Solution
Describe a branching vertex by the <first-order logic> sentence
$$
\beta=\exists x\exists y\exists z\,[E(x,y)\land E(x,z)\land y\ne z],
$$
and the existence of a sink by $\delta=\exists x\forall y\,\neg E(x,y)$. The directed path has sinks but no branching vertex; the directed cycle has neither sinks nor branching vertices; the directed arborescence has a branching vertex. Thus the following three sentences distinguish the named structures in order:
$$
\boxed{\varphi_1=\delta\land\neg\beta,\qquad\varphi_2=\forall x\exists y\,E(x,y),\qquad\varphi_3=\beta.}
$$
Here $\beta,\delta$ are abbreviations for the displayed formulas; replacing them gives sentences in the single-relation <first-order signature> $\{E\}$. Explicitly, $\varphi_1$ says that some vertex has no successor and that no vertex has two distinct successors. The <truth table> across the three structures is:
|| Sentence
|| $\mathcal G_1$
|| $\mathcal G_2$
|| $\mathcal G_3$
| $\varphi_1$
| $1$
| $0$
| $0$
| $\varphi_2$
| $0$
| $1$
| $0$
| $\varphi_3$
| $0$
| $0$
| $1$
The conditions distinguish these three finite structures; they are not claimed to characterize all directed paths, cycles or trees among arbitrary <directed graphs>. Only local <out-degrees> and the presence of a sink are needed, without quantifying over paths of unbounded length.
Back to article page
