which book are you studying go through books on graph theory like bondy and murthy , diestel, West try and then tell to vs140580@gmail.com
Hi,
I have the following definition of a edge cut for a graph, but I am unsure on some of the aspects of it:
"For a nonempty proper subset S ⊂ V(G) we let [S, ¬S] denote all the edges of G with exactly one end vertex in S. This set is called an edge cut of G.
An edge cut with k edges is called a k-edge cut"
The main part I don't understand is the [S, ¬S], ok so assuming there is a graph (G) is;
S = to the verticies that have one incident edge to be cut?
¬S = all the other vertices in G?
how does the [S, ¬S] denote edges?
Assume we have a 2d-cube graph V = {u,v,w,x} E = {uv, uw, wx, vx} then removing edges uv and vx create a vertex cut, but is this allowed as u has been used twice (has two end verticies in S??) so..
S = {u, x} ¬S = {w v}?
An example question was:
Note: # = lamda; edge connectivity; the smallest k for which G has a k-edge cut.
€ = small delta; minimum degree vertex in G
In the graph G, [S, ¬S] is a #(G)-edge cut with |S| = 2.
Prove: #(G) >= 2 €(G) − 2.
Thanks
which book are you studying go through books on graph theory like bondy and murthy , diestel, West try and then tell to vs140580@gmail.com