Combinatorics and Graph Theory · Problem 5.11.1

Graph Theory — David Guichard

Mathematics — Combinatorics · directed-graphs-connectivity

Problem

Connectivity in digraphs turns out to be a little more complicated than connectivity in graphs. A digraph is connected if the underlying graph is connected. (The underlying graph of a digraph is produced by removing the orientation of the arcs to produce edges, that is, replacing each arc (v,w)(v, w) by an edge {v,w}\{v, w\}. Even if the digraph is simple, the underlying graph may have multiple edges.) A digraph is strongly connected if for every vertices vv and ww there is a walk from vv to ww. Give an example of a digraph that is connected but not strongly connected.

Related theory

Browse the problem library