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