Althöfer, Ingo Average distances in undirected graphs and the removal of vertices. (English) Zbl 0688.05045 J. Comb. Theory, Ser. B 48, No. 1, 140-142 (1990). P. M. Winkler conjectured that every connected graph G contains a vertex k such that the removal of k and all incident edges enlarges the average distance between vertices of G by at most the factor 4/3. The authors prove that every m-connected graph was a vertex whose removal increases the average distance in the graph by no more than a factor of \(m/(m-1).\) This proves Winkler’s conjecture for 4-connected graphs. Reviewer: R.G.Stanton Cited in 12 Documents MSC: 05C38 Paths and cycles Keywords:average distance PDFBibTeX XMLCite \textit{I. Althöfer}, J. Comb. Theory, Ser. B 48, No. 1, 140--142 (1990; Zbl 0688.05045) Full Text: DOI References: [1] Berge, C., (Graphs and Hypergraphs (1976), North-Holland: North-Holland Amsterdam) · Zbl 0483.05029 [2] Winkler, P. M., Mean distance and the “Four-thirds Conjecture,”, (Congr. Numer., 54 (1986)), 63-72 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.