```*****  To join INSNA, visit http://www.insna.org  *****

DEAR COLLEAGUES WITH EXPERTISE IN MATHEMATICAL GRAPH THEORY:

I am sure that you are familiar with MENGER'S THEOREM (1), once
recalled to the SNA community by Steve Borgatti at the end of his
'Quorum of Graph Theoretic Concepts' (Connections 17/1 (1994):
47-49).

(1)  For any connected (undirected) graph G=(N,L) (L is a
subset of P2(N)=the set of 2-element subsets of a
finite set N), and any two nonadjacent points p and q,
the minimum number of points that must be removed
in order to break all paths joining p and q in G is
equal to the maximum number of point-disjoint paths
joining p and q.

DOES ANYBODY KNOW A PROOF OF (1) SIMPLER AND SHORTER THAN THAT
GIVEN IN CHAPTER 5 OF HARARY'S 'GRAPH THEORY' (1969)?

I would like to place a proof of Menger's theorem in my book
('The Mathematics of Exchange Networks', in process) to make my
theory exposition self-contained. I need Menger's theorem to
derive two other famous theorems.

(2)  Let a0(G) denote the 'point covering number' of G: the
minimum number of points which cover all lines of G
('a point covers a line if it is one of its
endpoints'). Let b1(G) denote the 'line independence
number' of G: the maximum number of pairwise disjoint
lines of G. For any bipartite graph G, a0(G)=b1(G).

(3)  Let G(A) stand for the set of lines of G=(N,L) with
one endpoint in A and the other in N-A. Let G be a
bipartite graph, that is, N is the union of two
disjoint sets N1 and N2 such that every line in L has
one endpoint in N1 and the other in N2. If |G(A)|>=|A|
for any subset A of N1, then b1(G)=n1.

I can easily prove that (1)=>(2)=>(3). A relatively simple proof
of (3) is given in an old book by Ore ('Graphs and Their Uses',
1963).

IS IT POSSIBLE TO DERIVE (1) FROM (3)?

Regards,

**********************************************************************
Tadeusz SOZANSKI, Ph.D.        JAGIELLONIAN UNIVERSITY, POLAND
INSTITUTE OF SOCIOLOGY         Phone: (48)(12) 6631734
Chair of Research on             Fax: (48)(12) 4302099