The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+3 votes
What is the vertex connectivity and edge connectivity of complete graph?

Is it n or n-1?
in Graph Theory by Boss (24.9k points)
edited by | 298 views
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 3,

1 Answer

+5 votes
Best answer

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

by Active (2.9k points)
selected by

Related questions

+7 votes
1 answer
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,362 questions
55,786 answers
90,918 users