Xref: utzoo sci.math:12255 comp.theory:1016
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uwm.edu!ux1.cso.uiuc.edu!osiris.cso.uiuc.edu!pjm
From: pjm@osiris.cso.uiuc.edu (P.McGuinness)
Newsgroups: sci.math,comp.theory
Subject: Re: Vertex Disjoint Paths in a graph
Message-ID: <1990Sep6.194702.24098@ux1.cso.uiuc.edu>
Date: 6 Sep 90 19:47:02 GMT
References: <8727@ccncsu.ColoState.EDU>
Sender: news@ux1.cso.uiuc.edu (News)
Organization: University of Illinois at Urbana
Lines: 25

srimani@webber.CS.ColoState.Edu (pradip srimani) writes:

>I have a problem as follows: Consider a symmetric graph G of
>vertex connectivity m. Then consider an arbitrary vertex s and
>another set of m arbitrary vertices d1, d2, ... . Is it true
>that we can always find vertex disjoint paths from s to each
>of these vertices di ? I can't prove or disprove it. If the
>claim is not true, is it true in case of vertex symmetric
>graphs of connectivity m ?

It is true in general, that a graph G is m-connected if and only if
it has m vertex-disjoint paths from any vertex s in G to any
set of m vertices in G-s.

This theorem is an extension of Menger's theorem, and is due
to Dirac. Menger's theorem states that a graph is m-connected
if and only if it has m vertex-disjoint paths between any pair
of vertices in G.  Using Menger's theorem, the result is actually not
difficult to obtain.
See Bollobas' " Extremal Graph Theory", p. 10  for details.

>Pradip K Srimani

Patrick McGuinness
Beckmann Institute, University of Illinois