# Thread: Graph Theory - Edge Cut / Connectivity

1. ## Graph Theory - Edge Cut / Connectivity

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

2. 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