Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prove that for any graph G, the connectivity is less that the minimum degree

  1. Oct 23, 2012 #1
    prove that for any graph G, kappa (G) ≤delta (G).
     
  2. jcsd
  3. Oct 23, 2012 #2

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper

    define your terms.
     
  4. Oct 27, 2012 #3
    suppose the connectivity is larger than min deg and look at the vertex v with min deg.
    How many elements (nodes / edges) need to be removed to disconnect v from the rest of G?
     
  5. Oct 27, 2012 #4

    Bacle2

    User Avatar
    Science Advisor

    What about the graph {(x,y)} on two vertices {x,y}, i.e., a tree with one edge?

    EDIT: OP, you may want to square up your title with your question. Do you want less-than, or less-than-or-equal-to?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Prove that for any graph G, the connectivity is less that the minimum degree
  1. Connected Spaces (Replies: 5)

  2. Connected Sets (Replies: 7)

  3. Connections and forms (Replies: 12)

Loading...