... caterpillar1
A caterpillar is a tree in which a single path (the spine) is incident to (or contains) every edge.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... graph2
The underlying undirected graph is obtained from the digraph by removing the direction on the arcs. So the number of edges in the underlying undirected graph is the number of arcs in the digraph.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... connected3
Such a digraph is often called weakly connected.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.