1 Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University2 University of Aarhus. Basic Research in Computer Science, Centre of the Danish National Research Foundation3 Department of Operations Research, Eotvos University
Let D = (V,E) be a minimally k-edge-connected simple directed graph. We prove that there is a function f(k) such that |V| ≥ f(k) implies |E| ≤ 2k(|V| - k). We also determine the external graphs whose graphs whose size attains this upper bound.
Technical Report of the Egerváry Research Group on Combinatorial Optimization, 2002, Issue TR-2002-10, p. 1-13