Self Doubt

Question

Why is the vertex connectivity of a graph always less than or equal to its edge connectivity?

Comments

https://cs.stackexchange.com/a/109401/141272
 

---

read this but not getting.

Answer 1

A vertex can be corresponds to many edges. When we remove one vertex there is high probability that graph become disconnected . On other side a edge is only corresponds to two vertex , which has less probability of making graph disconnected .

Comments

Thanks..but this is not proof..Can you prove it by contradiction.

Answer 2

@raja11sep

The vertex-connectivity of a graph is less than or equal to its edge-connectivity…

That is, κ(G) ≤ λ(G)....

Both are less than or equal to the minimum degree of the graph, since deleting all neighbors of a vertex of minimum degree will disconnect that vertex from the rest of the graph...

 

1. https://gateoverflow.in/26307/That-edge-connectivity-less-equal-minimum-degree-vertex-graph 

 

2. https://en.wikipedia.org/wiki/Connectivity_(graph_theory)

 

 

Comments

thanks