Results 1 to 2 of 2

Math Help - Problems about connectivity

  1. #1
    Newbie
    Joined
    May 2010
    Posts
    2

    Problems about connectivity

    Hi,

    Can you help me to prove the following statements?

    (1) Let G be a graph. Prove that if d(G)=p-2, then K(G)=d(G)
    (2) Prove that if G is connected, then K(G)=1+min{K(G-v):v is a vertex of G}

    In any case, d(G) is the minimum vertex degree, p the number of vertices and K(G) the minimum k for which G has a k-vertex cut
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    May 2010
    Posts
    98
    A lil' tip. k(G) is less than or equal to d(G) for all graphs
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Connectivity Graphs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 30th 2010, 02:34 AM
  2. Continuous and connectivity
    Posted in the Differential Geometry Forum
    Replies: 9
    Last Post: March 14th 2010, 04:01 PM
  3. Connectivity
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: February 1st 2010, 04:18 AM
  4. connectivity question in R^{n}
    Posted in the Differential Geometry Forum
    Replies: 9
    Last Post: January 5th 2010, 05:33 PM
  5. Edge Connectivity
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: May 29th 2008, 06:08 AM

Search Tags


/mathhelpforum @mathhelpforum