Results 1 to 2 of 2

Math Help - Graph Theory - Edge Cut / Connectivity

  1. #1
    Newbie
    Joined
    May 2009
    Posts
    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Jul 2009
    Posts
    8
    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph Theory- Edge Colouring
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 4th 2011, 12:20 AM
  2. Graph Edges and Connectivity
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 3rd 2011, 04:55 AM
  3. connectivity 3 regular graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 30th 2010, 04:27 PM
  4. Graph connectivity proofs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: May 12th 2010, 12:11 PM
  5. Edge Connectivity
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: May 29th 2008, 06:08 AM

Search Tags


/mathhelpforum @mathhelpforum