A circular graph — counterexample to the Duchet kernel conjecture

AbstractWe construct a directed graph G such that (a) G is strongly connected, (b) G has the circular symmetry, (c) G is not a directed odd cycle but the union of three such cycles with the same set of vertices and pairwise disjoint sets of edges, (d) G has no kernel but (e) after removing any edge from G the resulting graph has a kernel. Thus not only the directed odd cycles are connected edge-minimal kernel-less directed graphs