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