## SOCNET@LISTS.UFL.EDU

#### View:

 Message: [ First | Previous | Next | Last ] By Topic: [ First | Previous | Next | Last ] By Author: [ First | Previous | Next | Last ] Font: Proportional Font

Subject:

Menger's theorem

From:

Date:

Wed, 2 Mar 2005 12:38:00 +0100

Content-Type:

text/plain

Parts/Attachments:

 text/plain (62 lines)
 ```***** 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.```