A proof of menger's theorem by contraction

• Autorzy: Frank Göring
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

connectivity; disjoint paths; digraph; Menger

Kategorie tematyczne

• 05C40: Connectivity

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2002
• Tom: 22
• Numer: 1
• Strony: 111-112

Daty

wydano

2002

otrzymano

2000-06-08

poprawiono

2001-05-21

Twórcy

autor

Frank Göring

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

Bibliografia

• [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.

Identyfikatory

DOI

10.7151/dmgt.1161