The number of edges in critical strongly connected graphs

Abstract

We prove that the maximal number of directed edges in a vertex-critical strongly connected simple digraph on n vertices is n(n-1)/2 - n +4.

5 pages, no figures, given at the Eleventh Haifa Matrix Theory Conference 26.5.1999 Accepted at Discrete Math. v1 is the submitted version, v2 is the version after the referee's corrections. Note the main correction: the result for edge critical strongly connected graphs is already known