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

  • Context: Graduate 
  • Thread starter Thread starter sunnyceej
  • Start date Start date
  • Tags Tags
    Degree Graph Minimum
Join the discussion
Registration is free. Ask a follow-up in this thread, or start your own.
3 replies · 3K views
sunnyceej
Messages
15
Reaction score
0
prove that for any graph G, kappa (G) ≤delta (G).
 
Physics news on Phys.org
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?
 
sunnyceej said:
prove that for any graph G, kappa (G) ≤delta (G).

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?