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


    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


    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?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook