Article contents
Short proof of Menger's graph theorem
Published online by Cambridge University Press: 26 February 2010
Extract
The object of this paper is to give a simple proof of Menger's famous theorem [1] for undirected and for directed graphs. Proofs of this theorem have been given by D. König [2], G. Nöbeling [3], G. Hajós [4], T. Gallai [5], P. Erdös [6] and 0. Ore [7]. The present proof is shorter, and formulated to apply to directed and undirected graphs equally. The term, graph is to be understood to mean either a finite undirected graph or a finite directed graph throughout. (A: B) denotes either an undirected edge between the two vertices A and B or a directed edge from A to B according to whether undirected or directed graphs are considered. G1 and G2 being two non-empty disjoint graphs, G1: G2-edge denotes an undirected edge between a vertex of G1 and a vertex of G2 or a directed edge from a vertex of G1 to a vertex of G2 as the case may be, and G1: G2-path denotes a path with one end-vertex in G1 and one in G2 having no intermediate vertex in G1 + G2, undirected or directed from the end in G1 to the end in G2, as the case may be. (A set of isolated vertices is a graph.)
- Type
- Research Article
- Information
- Copyright
- Copyright © University College London 1966
References
- 27
- Cited by