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

sunnyceej
Messages
15
Reaction score
0
prove that for any graph G, kappa (G) ≤delta (G).
 
Physics news on Phys.org
define your terms.
 
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?
 
Back
Top