A proof of menger's theorem by contraction

Frank Göring

ArticleOriginal scientific text

Title

A proof of menger's theorem by contraction

Authors ¹

Affiliations

Department of Mathematics, Technical University of Ilmenau, D-98684 Ilmenau Germany

Abstract

A short proof of the classical theorem of Menger concerning the number of disjoint AB-paths of a finite graph for two subsets A and B of its vertex set is given. The main idea of the proof is to contract an edge of the graph.

Keywords

ENG

connectivity, disjoint paths, digraph, Menger

T. Böhme, F. Göring and J. Harant, Menger's Theorem, J. Graph Theory 37 (2001) 35-36, doi: 10.1002/jgt.1001.
W. McCuaig, A simple proof of Menger's theorem, J. Graph Theory 8 (1984) 427-429, doi: 10.1002/jgt.3190080311.
R. Diestel, Graph Theory (2nd edition), (Springer-Verlag, New York, 2000).
G.A. Dirac, Short proof of Menger's graph theorem, Mathematika 13 (1966) 42-44, doi: 10.1112/S0025579300004162.
F. Goering, Short Proof of Menger's Theorem, to appear in Discrete Math.
T. Grünwald (later Gallai), Ein neuer Beweis eines Mengerschen Satzes, J. London Math. Soc. 13 (1938) 188-192, doi: 10.1112/jlms/s1-13.3.188.
K. Menger, Zur allgemeinen Kurventheorie, Fund. Math. 10 (1927) 96-115.
J.S. Pym, A proof of Menger's theorem, Monatshefte Math. 73 (1969) 81-88.

Title

A proof of menger's theorem by contraction

Affiliations

Abstract

Keywords

Bibliography