Path: csiph.com!aioe.org!.POSTED!not-for-mail
From: Daniel Bastos <dbastos@toledo.com>
Newsgroups: comp.programming,alt.algebra.help
Subject: on cut edges and bonds, graph theory
Date: Mon, 18 Sep 2017 12:51:42 -0300
Organization: Aioe.org NNTP Server
Lines: 32
Message-ID: <86wp4w3sz5.fsf@toledo.com>
NNTP-Posting-Host: tIKNYGSzQvz1vCekatgPFA.user.gioia.aioe.org
Mime-Version: 1.0
Content-Type: text/plain
X-Complaints-To: abuse@aioe.org
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (windows-nt)
X-Notice: Filtered by postfilter v. 0.8.2
Cancel-Lock: sha1:q6Pg5d4arl75X3jT6rllruMOPNU=
Xref: csiph.com comp.programming:8011 alt.algebra.help:4999

This is a question on the definition of cut edges, edge cuts and bonds
as given by section 2.2, page 27-29 of

  ``Graph theory with applications'' by J.A. Bondy and U.S.R. Murty,
  Department of Combinatorics and Optimization, University of Waterloo,
  Ontario, Canada.  North-Holland, fifth printing, 1982.  ISBN:
  0-444-19451-7.

I understand cut edges.  It's defined in page 27.

Definition (cut edge).  A cut edge of G is an edge e such that 
w(G - e) > w(G), where w(G) means the number of components of G.

It says e is a a cut edge if removing e from G yields more components
than we had before.  In other words, e is necessary to keep G with the
components it had.  (In particular, if G is connected, then e is
necessary to keep G connected.)

No problem here.

On page 29, edge cuts are defined.  (My writing.)

Notation (separation).  For subsets S and S' of V, we denote [S, S'] the
set of edges with one end in S and the other in S'.

Question.  It seems [S, S'] is a separation of G into two parts.  Does
it mean [S,S'] contains all possible (x,y) edges for x in S, y in S'?

Although the book gave me Figure 2.4 (a), it didn't give me S and S', so
I'm not sure which vertices of the picture would be in S.

Thank you!