The Gateway to Computer Science Excellence
+3 votes
What is the vertex connectivity and edge connectivity of complete graph?

Is it n or n-1?
in Graph Theory by Boss
edited by | 316 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
selected by
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
52,218 questions
59,890 answers
118,128 users