Graph Theory: Cuts, Minimal Cuts and Bonds

Hello,
I'm confused in definitions of these terms. Can anyone give me some
explantions?

These definitions are from Reinhard Diestel's "Graph Theory, 3rd
Edition" book.

Minimal with some property:
The books says "More generally, when we call a graph minimal or
maximal with some property, but have not specified any particular
ordering, we are reffering to the subgraph relation. When we speak of
minimal or maximal sets of vertices or edges, the reference is simply
to set inclusion."

E(X,Y) set:
If x is from X and y is from Y (vertices), then we call the edge xy
from E an X-Y edge. We denote the set of this edges in E (edge set of
graph) by E(X, Y). Instead of E{{ x }, V) and E(X, {y}) we simply
write E(x,Y) and E(X,y). The set of all the edges in vertex v is
denoted by E(v).

Cut:
"If {V1,V2} is a partition of V the set E(V1,V2) (already defined, see
above) of all the edges of G crossing(defines 'crossing') this
partition is called a cut (or cocycle). Recall that for V1={ v} this
cut is denoted by E(v)."

Bond:
"A minimal non-empty cut in G is a bond."

By these definitions, I suppose that every cut is a minimal(with a
fixed partition). I mean, if we remove some edges from our cut, the
remaining edges cannot form a cut with the same partition(or, which is
the same, there's no subset of a cut that forms a cut with the same
partiton). Thats true for any cut, so any cut is a minimal. Thus every
non-empty cut is a bond???

Thanks,
Narek Saribekyan

.

Relevant Pages

  • Re: Graph Theory: Cuts, Minimal Cuts and Bonds
    ... On Aug 17, 1:15 pm, Narek Saribekyan ... These definitions are from Reinhard Diestel's "Graph Theory, ... We denote the set of this edges in E (edge set of ... partition is called a cut. ...
    (sci.math)
  • Re: vertices in graph vertex covers
    ... A graph where every vertex is of degree 2 ... a partition shares an edge with another ... Dependent: A variable where the assignment depends on ... For every satisfying assignment where v ...
    (sci.math.research)
  • Constructing Quotient Graphs
    ... If we partition N into k parts. ... We define the "Quotient graph" with respect to the above partition as: ... running time O+size). ...
    (comp.programming)
  • Graph Partitioning Problem
    ... I have an application where I want to find a minimum weight partition ... of an undirected graph into k connected components such that each ... All the graph partitioning algorithms and programs I've seen ... Does anybody know of any algorithms, ...
    (comp.theory)
  • Re: combinatorics/graph theory problem for set partitions
    ... >Suppose I construct a random graph by choosing k edges in such a way ... >that each edge is chosen independently with probability p, ... >Then I consider the set partition defined by this graph such that two ...
    (sci.math)