[Discrete Maths] Graph theory

Question

What is the vertex connectivity and edge connectivity of complete graph?

Is it n or n-1?

Comments

Extra information:

vertex connectivity <= edge connectivity <= minimum degree of graph

Example of are them being equal?

Ex : For Q3 (Cubic graph) all of them are equal.to 3,

Answer 1

Its N-1 
Vertex Connectivity means minimum Number of vertices needed to be removed to disconnect the graph or make it a trivial graph 
Trivial Graph means graph with only one node 
Edge Connectivity means minimum number of edges that must be removed to disconnect the graph 
In case of complete graph min degree of any node is n-1 so you need to remove at least  n-1 edges

Comments

Hii @aehkn If we remove n-1 vertices from the graph, we left only 1 vertix in the graph and as we know single vertix graph itself is a connected graph so in case of complete graph Edge Connectivity is n-1 and vertix connectivity is not defined.

 

---

The minimum number of vertices whose removal makes ‘G’ either disconnected or reduces ‘G’ in to a trivial graph is called its vertex connectivity. Trivial graph means a graph with single vertices, which is the case here.

@lalitver10

---

@raja11sep furfect