***** 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,

Tad Sozanski

**********************************************************************
  Tadeusz SOZANSKI, Ph.D. JAGIELLONIAN UNIVERSITY, POLAND
  INSTITUTE OF SOCIOLOGY Phone: (48)(12) 6631734
  Chair of Research on Fax: (48)(12) 4302099
  Group Processses, rm.49 Email: [log in to unmask]
  52 Grodzka, 31-044 Krakow Http://www.cyf-kr.edu.pl/~ussozans/
**********************************************************************

_____________________________________________________________________
SOCNET is a service of INSNA, the professional association for social
network researchers (http://www.insna.org). To unsubscribe, send
an email message to [log in to unmask] containing the line
UNSUBSCRIBE SOCNET in the body of the message.