[comp.theory] Vertex Disjoint Paths in a graph

srimani@webber.CS.ColoState.Edu (pradip srimani) (09/06/90)

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 ?

I'll be grateful if anyone can give me any pointers to
existing literature or throw any light on the problem. Thank
you so much.

Pradip
=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=

Pradip K Srimani
Department of Computer Science

pjm@osiris.cso.uiuc.edu (P.McGuinness) (09/07/90)

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