Discussiones
Mathematicae Graph Theory 22(1) (2002) 111-112
DOI: https://doi.org/10.7151/dmgt.1161
A PROOF OF MENGER'S THEOREM BY CONTRACTION
Frank Göring
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: connectivity, disjoint paths, digraph, Menger.
2000 Mathematics Subject Classifications: 05C40.
Received 8 June 2000References
[1]
T. Böhme, F. Göring and J. Harant, Menger's Theorem, J. Graph Theory 37
(2001) 35-36, doi: 10.1002/jgt.1001.
[2]
W. McCuaig, A simple proof of Menger's theorem, J. Graph Theory 8 (1984)
427-429, doi: 10.1002/jgt.3190080311.
[3]
R. Diestel, Graph Theory (2nd edition), (Springer-Verlag, New York, 2000).
[4]
G.A. Dirac, Short proof of Menger's graph theorem, Mathematika 13 (1966)
42-44, doi: 10.1112/S0025579300004162.
[5]
F. Goering, Short Proof of Menger's Theorem, to appear in Discrete Math.
[6]
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.
[7]
K. Menger, Zur allgemeinen Kurventheorie, Fund. Math. 10 (1927) 96-115.
[8]
J.S. Pym, A proof of Menger's theorem, Monatshefte Math. 73 (1969) 81-88.
Revised 21 May 2001
Close